Yep, USB connection is possible. Not only that, it is also the most reliable connection. When you want to use a keyboard connected to the RasPi, I guess running a "normal" Xorg server, probably with a virtual framebuffer as output, and then x11vnc on top of that. That is because I have no quick idea on how to connect to a pure-VNC X server (such as Xvnc). Well, I actually do have an idea: Write a simple input-only vnc client that reads from Linux input devices. This would be simple, however, it doesn't exist yet. Except: The viewer featured by this thread could probably easily trimmed down to do exactly this when compiled for the RasPi.
Edit/Addendum: That would really make a funny duo. Hm, don't they both run a linux on ARM?