Algumas opções.
1) Que tal um túnel SSH reverso?
link É simples e funciona por trás do NAT.
Experimente e veja se funciona.
Não tenho certeza se você precisa saber o IP de origem sempre. Isso pode ser um problema.
2) Teamviewer para linux.
A maneira como o teamviewer trabalha é que ele inicia um serviço que se conecta ao host do teamviewer (algo que você não precisa se preocupar).
Você simplesmente usa o ID gerado automaticamente para acessar a máquina com uma senha.
Você pode bloquear o serviço TeamViewer para que os usuários não consigam alterá-lo também.
Ele oferece uma experiência completa na área de trabalho. Não sei se isso é um problema para você ou não.