There are several ways to achieve this - STUN , TURN , ICE , to name a few. You can read about each of them, and software such as skype, gtalk, etc., uses these methods among others.
But the basic concept that needs to be understood here is
You need an ip available to the public so you can connect to it. If it is located behind a router on a private network, you need port forwarding on the router, that is, you need to add a rule to this router to forward traffic received on a specific port to your server behind the router. To a certain extent, the above methods achieve this implicitly or by involving an external third-party server.
You need to allow incoming connections on the machine to which it is first connected. Typically, Windows or linux firewalls block all incoming connections unless an exception is added. This will probably be needed for both of your nodes.
In the last part, I do not program on android, so I'm not sure that it allows you to add rules for incoming connections, etc. But I know that gtalk has a client for android, and gtalk uses XMPP, which internally can use any of those methods that I indicated above. Therefore, there is no reason to believe why this cannot be done for an Android phone.
Adding a few more useful links:
libjingle is a google open source library that can be used to write p2p applications, including text, audio and video.
It seems that it was compiled for android, but here
fayyazkl
source share