There is a very cool command line utility called
cscreen. The developer has a number of versions available. Depending on how old your Mac is, you either want the PPC version, or the Intel version. If your Mac is newer than a 2006 model, you probably want the Intel version.
Once you have downloaded the disk image, double click the image to mount it, then copy the cscreen file to anywhere except the disk image. Now open Terminal. (You can search for it in Spotlight.) Once Terminal is open, you can run
cscreen by navigating to it, then typing
./cscreen. For example, if you copied cscreen to your Desktop, you would navigate to the Desktop in Terminal by typing
cd ~/Desktop. Once there, you would type
To change the resolution, we first need to know what resolutions are possible. To find out, we can type
./cscreen -v. This should output something like this:
Now we can choose a resolution. Assuming you want 32 bit colour depth, you can change to the resolution of your choice by typing
cscreen -i <DisplayID> -d 32 -x <width> -y <height>,
and replacing the parts enclosed in <> with the actual values. I haven't tested this with a headless system over VNC, so your milage may vary. The command line option
-i <DisplayID> is optional, so if your VNC doesn't register a display ID you may still be able to change the resolution if you omit that part of the command.