UPnP requires software support in your router. Even when routers have it, it's sometimes turned off due to security concerns.
STUN uses a simple public server to detect the presence of NAT and the real IP addresses. This is useful for other, higher-level protocols that do the useful work.
Hole punching is a simple technique to connect two computers. It requires a 3rd public computer to communicate between the 2 computers behind NAT. You could run your own server with a custom protocol, our you could use STUN and existing STUN servers. (Only a few packets are needed for setup, the rest are peer-to-peer).
Of course, some NAT firewalls are incompatible with the above, so you may need a custom protocol. Bittorrent does this: they use different techniques depending on which clients are behind firewalls and whatnot.