To punch the whole, isn't there a TURN server or something? How do you establish a p2p connection if one of the devices is behind a NAT?

Exactly why it's called holepunch. It fuzzes firewall protocols with certain packets and timing to convince firewalls that it's an acceptable stream of data regardless of the firewall settings. I saw a conference talk on it a while ago. It was super interesting