Mosh
I have to ssh proxy to get to my main machine, everything is filtered on the network my machine is on, apart from the ssh access box. This makes using mosh a little troublesome.
                          +-------+           
+------+                  |ssh    |          +-----------+ 
|laptop|-------ssh------->|gateway|--ssh---->|           | 
+------+<--               +-------+          |dev machine| 
           \---------mosh------------------->|           | 
                                             +-----------+
dev can only be reached via an ssh proxy, but thankfully there is an open UDP port range that works. Mosh seems to have trouble figuring out the correct ip/port pair to select in this setup, mosh is quite simple so it is easy to deal with.
Host dev
Hostname dev.domain.tld
User tj
ProxyCommand ssh -w 30 -q gateway.domain.tld nc %h 22
 The
 
  mosh
 
 command is just a shell script, it sshs to the remote machine and
runs
 
  mosh-server
 
 . Mosh server generates an AES session key and starts the
mosh server process on the machine.
 
  mosh-client
 
 takes the session key via an
environmental variable, ip address and port the server is listening on.
With that we can run mosh by hand:
[laptop] $ ssh dev
[dev] $ mosh-server
  setsockopt( IP_RECVTOS ): Invalid argument
  MOSH CONNECT 40001 pv2jeN0MJ1N4gCd1V0i21g
  mosh-server (mosh 1.2.5) [build mosh 1.2.5]
  Copyright 2012 Keith Winstein <mosh-devel@mit.edu>
  License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
  This is free software: you are free to change and redistribute it.
  There is NO WARRANTY, to the extent permitted by law.
  [mosh-server detached, pid = 19100]
  Warning: termios IUTF8 flag not defined.
  Character-erase of multibyte character sequence
  probably does not work properly on this platform.
[dev] $ exit
[laptop] $ MOSH_KEY="pv2jeN0MJ1N4gCd1V0i21g"
[laptop] $ mosh-client 143.100.67.5 40001
Once you know how to do mosh by hand there are other things we can try. I don't think it would be impossible to work around certain types of NAT using nc. It requires a third party box, but a lot of STUN can be done with just UDP packets.
Reading: Little Brother, Transmetropolitan
I am sure I have written this down before, google couldn't find it.