É possível usar o VNC para se conectar a um servidor sem efetuar login primeiro, mas não com a configuração VNC padrão que vem com o Ubuntu Desktop.
Nomachine NX pode ser uma boa escolha. É um servidor de terminal que funciona através de SSH e fornece acesso remoto X de alta velocidade para que você possa executar quase qualquer aplicação GUI de outro PC. Ele não suporta 3D, então usar coisas como Compiz, Gnome-shell ou Unity não funciona, mas a maioria das outras coisas funciona. Eu usei-o para executar o OpenOffice.org em um navegador, por exemplo (o que é realmente muito bom).
X2Go é outra alternativa que usa bibliotecas Nomachines, mas está melhor integrada ao Ubuntu, com suporte a PulseAudio, etc. Se seus clientes são principalmente baseados em Windows, o Nomachine pode ser uma escolha melhor, mas se você usar o Ubuntu em seus clientes, então X2go é melhor. O X2go é um software totalmente gratuito, enquanto o Nomachine NX é de código fechado, mas oferece um servidor gratuito que permite que dois usuários diferentes acessem o servidor, limitado a duas conexões ao mesmo tempo.
Você pode encontrar o X2go aqui: link
Nomachine: link
Existe também uma terceira alternativa: Xrdp. Não foi muito maduro da última vez que usei, e parece estar mal documentado, mas deve funcionar muito bem. A vantagem de usá-lo é que muitos sistemas vêm pré-instalados com um cliente RDP, portanto, você não precisa instalar nada no lado do cliente.
Se você planeja usar isso extensivamente, então eu sugiro que você experimente todos eles e veja qual deles se encaixa melhor.