It is possible to use VNC to connect to a server without logging in first, but not with the default VNC setup that comes with Ubuntu Desktop.
Nomachine NX might be a good choice. It is a terminal server that works over SSH and provides you with high-speed remote X access so you can run almost any GUI-application from another PC. It does not support 3D, so using things like Compiz, Gnome-shell or Unity does not work, but most other stuff works. I've used it to run OpenOffice.org in a browser, for instance (which is really quite nice).
X2Go is another alternative that uses Nomachines libraries, but is better integrated with Ubuntu, with PulseAudio support, etc. If your clients are primarily Windows based, then Nomachine might be a better choice, but if you use Ubuntu on your clients, then X2go is better. X2go is completely free software, whereas Nomachine NX is closed source, but provides a gratis server that allows two different users to access the server, limited to two connections at any one time.
You can find X2go here: http://www.x2go.org/index.php?id=1&L=5
Nomachine: http://www.nomachine.com/
There is also a third alternative: Xrdp. It wasn't very mature the last time I used it, and it seems to be poorly documented, but it is supposed to work very well. The advantage of using it, is that many systems come preinstalled with an RDP client, so you don't have to install anything on the client side.
If you plan on using this extensively, then I would suggest you give all of them a try and see which fits best.