En principio necesitas uno o varios puertos redirigidos al PC en cuestión, para que el enrutador sepa a qué equipo ha de enviar los paquetes.
Si el router soporta el paso de túneles VPN, tendrías el problema más que solucionado, pero aún soportando VPN pass-through, necesitas tener acceso al enrutador para redirigir los puertos a la máquina Ubuntu.
¿Software? Pues desde VNC, hasta OpenVPN, pasando por cualquier servidor FTP libre.
Pero ya te digo que si no puedes meter mano al router/firewall, lo tienes un poquito jodido.