Figured it out myself, finally.
Apparently the problem was that since there is no monitor, no valid "screens" are started up when the box boots, and therefore no resolutions are available in the Unity settings dialog.
However, when no screens are found, it seems the system defaults to a "virtual desktop", with a 640x480 resolution. The system does support virtual desktops that have different resolutions than the connected monitors (in this case none), so the trick was to change the default virtual desktop resolution. That can be done in the /etc/X11/xorg.conf.
My file currently looks like this.
Section "Device"
Identifier "Default Device"
Option "NoLogo" "True"
EndSection
Section "Monitor"
Identifier "Configured Monitor"
EndSection
Section "Screen"
Identifier "Default Screen"
Monitor "Configured Monitor"
Device "Default Device"
SubSection "Display"
Depth 24
Virtual 1280 800
EndSubSection
EndSection
This seems to suffice, and you can change the "Virtual 1280 800" section to whatever you want. And the reboot the box. I am using the built-in vino VNC server.