samy.pl/pwnat
pwnat, descendant of udptunnel (from Daniel Meekins dmeekins - gmail ; not the udptunnel from Debian repository)
(pwnat is also related to samy.pl/chownat , but implemented in C, and perhaps the perl version uses incompatible protocol)
is a very smart program. Pwnat aims to connect 2 hosts, both behind NAT.
Pwnat requires root privileges to send ICMP. Unfortunately even with such privileges, it did not work for me
under most circumstances (it worked about 1 in 10 cases; on networks where skype works 100%).
I was concerned that maybe on mobile broadband other clients use pwnat and send ICMP to 3.3.3.3
therefore I tested with different IP. Both pwnat server and client with same of course, see IP3333 hack.
Even with this, pwnat only worked about 1 in 10 cases.

To make it work in real life situations (and preferrably without root privileges; although that was not the main goal)
Marcell Gal wrote vemsfriend server.
vemsfriend server is a simple UDP rendezvous server (also provides client's IP so replaces STUN) running on $vfserver.
To make UDP query, vfclient, or even a 1-liner with standard socat can be used (see NAT2 below).
It was used with chownat.pl but I like pwnat. 
----
pwnat is patched to understand the autovf:... syntax:
patch -p1<pwnat.diff
Behind NAT1:
pwnat -s autovf:$vfserver:8078

Running as normal user, (or as root) it requests and receives partner IP successfully (from $vfserver),
and tcpdump confirms it is periodically sending
greeting 0 length UDP packets sport=2222 dport=2222 as it should, to create UDP pinhole in the NAT.

----
Behind NAT2:

PH=`vfclient $vfserver`;
# alternatively:
PH=`echo 'get udp:4321' | socat - udp:$vfserver:8078 | gawk 'NF {if(++CNT==3){print $1; exit 0;}}' `;
echo PH=$PH;
./pwnat -c 8022 $PH 127.0.0.1 22

Interestingly, disconnects prematurely even though
pwnat -c (udpclient.c) is standard, and peer IP is provided on the commandline
(no magic involved inside);
Remember, that even when run as root,
tcpdump shows that it does NOT send UDP packets to partner's 2222 port. It will only start sending UDP
when connection is started to the local listening TCP port !
Note: the pwnat -s side must also be started as root, currently.
PH=84.224.69.137
Listening on TCP 0.0.0.0:8022

I verified that UDP .2222 <=> .2222 passes through both ways.
echo PH=$PH; ./pwnat -v -v -c 8022 $PH 2222 127.0.0.1 22
PH=176.77.252.240
Listening on TCP 0.0.0.0:8022

Another pwnat -c cannot be run on same 2222 port ("Bind failed").

----
Conclusion:
* pwnat kinda works...
** not sure how robust. More tests are needed.
** DOS (connection teardown/disconnect by adversary: spoofed UDP packets) is probably easy.
** maybe not too bad; but I originally planned to make the patch small, simple, trivial and nonintrusive
* Maybe udptunnel should be patched also ?
** udptunnel is not binding to specific port. First attempt to use udpbindport() did not succeed:
--- udptunnel-orig/udpclient.c  2011-07-04 07:11:37.000000000 +0200
+++ udptunnel/udpclient.c       2015-01-02 23:29:47.000000000 +0100
@@ -39,4 +39,5 @@
 #include "client.h"
 #include "list.h"
+#include "vfclient.h"
 
 extern int debug_level;
@@ -186,4 +187,5 @@
             }
 
+            udpbindport(udp_sock->fd, 2222);
             client = client_create(next_req_id++, tcp_sock, udp_sock, 1);
             if(!client || !tcp_sock || !udp_sock)