O único NAT com o qual um túnel IPIP pode trabalhar é o NAT um-para-um, o que claramente não é o que você tem no caso do celular.
Esse negócio de "150 bytes / segundo para uma conexão SSH aberta" é muito estranho e você deve investigar. Isso não acontece comigo com o OpenSSH - > Sessões de OpenSSH (há as keepalives inevitáveis, mas você quer aquelas quando você está atrás de um NAT) e não há razão para isso, a menos que você esteja realmente passando tráfego.
Você está enganado porque o netcat está sendo unidirecional, uma sessão TCP iniciada com o netcat funciona nos dois sentidos.
Eu sugiro obter um fluxo bidirecional de qualquer maneira possível (provavelmente netcat e um ouvinte TCP no servidor) e executar o PPP sobre isso. Você obtém todas as desvantagens habituais de executar IP sobre TCP, mas é melhor do que não ter conectividade em tudo.
Veja o que funciona para mim em um teste rápido - no servidor:
server:~$ sudo pppd noauth passive pty "nc -lp 9999" debug nodetach
No cliente:
client:~$ sudo pppd noauth pty "nc server 9999" debug nodetach
Acho que ter a semântica de discagem também fornece um modelo útil para os casos em que seu dispositivo de célula simplesmente não pode ser acessado.
Depois de ter a conexão IP em execução, você pode considerar a reprodução de IPIP ou NAT 1: 1.