O tunelamento SSH reverso faria o truque - em suma, você obtém o computador que está por trás do nat conecte ao servidor ssh do outro sistema. Você teria que trabalhar de alguma forma para iniciar isso - possivelmente algum script rápido e sujo e crontab executando o processo para iniciar um túnel de vez em quando, ou usando um sistema sempre ativo como intermediário.
Uma alternativa seria configurar alguma forma de VPN livre de configuração que use outro servidor como intermediário - hamachi vem à mente, mas há outras alternativas que podem funcionar.
Editar: autossh pode automatizar o processo ssh reverso do sistema por trás do nat, o que tornaria as coisas mais simples