Found out that the vnc4server (4.1.1) shipped with Ubuntu (10.04) is patched to also support changing the resolution on the fly via xrandr. Unfortunately the feature was hard to find because it is undocumented. So here it is...
Start the server with multiple 'geometry' instances, like:
vnc4server -geometry 1280x1024 -geometry 800x600
From a terminal in a vncviewer (with: 'allow dymanic desktop resizing' enabled) use xrandr to view the available modes:
to change the resulution, for example use:
xrandr -s 800x600