Em resposta a minha própria pergunta, a maneira como consegui que isso funcionasse era a seguinte. Primeiro, eu usei um telefone Android com um cliente vpn de zimbro para se conectar à VPN. Então eu usb meu telefone ligado ao meu laptop. Mesmo que a internet no meu laptop está passando por cima do meu telefone (e, portanto, através do cliente vpn), ssh'ing do meu laptop para o computador remoto ainda não funcionaria. No entanto, usando o sistema de corda clockwordmod (que requer um aplicativo para o telefone e outro cliente para o laptop) me permitiu estabelecer uma conexão ssh do laptop. Eu não sei exatamente o que o clockworkmod está fazendo especial, mas acho que posso viver sem saber por tempo.