Android P2P (direct-connection) over the Internet (behind NAT)
use xmpp via smack over gtalk. You don't have to worry about server and single point of failure. let google worry about that! I have written Tetris to make it play against two player using gtalk as a communication layer. http://code.google.com/p/tetrads-drop-lite/ You can try MUC if you want more player.
UDP is not reliable delivery but a you can make it reliable by requiring that send UDP packets require acknowledgements be return. This, along with a few other requirements, is what makes TCP reliable over IP (which is unreliable to begin with).
As a note, this is possible to implement but will probably be time consuming and the cost/benefit may not work out in your situation.
You're pretty much forced to use an intermediary. You can look up Natblaster for a mechanism that will work for establishing TCP connections between some NATed devices, but it's not something that you can use in Android without rooting both devices. And even then, it's experimental.
The best is probably to use an existing federated messaging system like jabber.