android socket programming behind a router
There are several techniques to achieve this - STUN, TURN, ICE to name a few. You can read about each of them and softwares such as skype, gtalk (now google talk Mar 2018) etc. use these techniques among others.
But the primary concept to understand here is,
You need an ip which is publicly reachable so that you can connect to it. If it is behind a router on a private network, then you need port forwarding on the router i.e. you need to add a rule to that router to forward traffic received on a particular port to your server behind the router. To a certain extent, the above techniques achieve this implicitly or by involving an external 3rd party server.
You need to allow incoming connections on the machine which is connected to at first. Generally windows or linux firewalls block all incoming connections unless an exception is added. This would probably be needed for both of your nodes.
For the last part, i don't program on android so am not really sure if it allows adding rules for incoming connections etc. But i do know that gtalk has a client for android and gtalk uses XMPP which internally can use any of the techniques i pointed out above. So there is no reason to believe why it can't be done for android phone.
Adding some more useful references:
libjingle (updated the link Mar 2018) is an open source library by google which can be used to write p2p applications including text, audio and video.
It seems to have been compiled for android as well here