since our game is p2p, one vs one game, we are planning to implement our game in a peer to peer manner wherein there is no central game server but instead the users will just host it on his phone and the challenger will just connect to his him thru sockets.

There will be a central database to handle stats, authentication, etc. (implemented thru firebase).

more or less looks like this

So here are the flow in a nutshell.

1. when user logs in to the game, his IP address will be logged in the firebase database.

2. the user is presented with a list of users online to challenge. when use clicks on a player, the user issues a challenge.

when the challenged player accepts the challenge, the user connects to him directly. 

Now, my issue.

This works if both or all users are in the same network since their IP will be unique, but if say for example, we are playing across internet,

there is a chance that 1 or two users will have the same IP (when using public IP) when two players are in the same network (ex: office wifi)

Situation 1:
both user1 and user2 uses mobile data, both of them has public IP (no issue)

Situation 2:
user1 uses mobile data, user2 uses office wifi, user2 shared the same public IP to his officemate.

user1 and user2 play against each other with no issue, but what happen if,

say user3 who shares the same wifi with user2 also wants to connect and challenge somebody in the game,

he uses the same IP address therefore there is an issue if we somebody needs to connect to that IP address since two users share the same public IP.

Also, to help the discussion we are using native (linux) sockets in C++ in both iOS and Android.

Any tips on how to handle this? How does applications working with peer to peer handle this?

Two things:

1) Firebase claims: "Data is stored as JSON and synchronized in realtime to every connected client."

This may sound convenient, but it means that every client will be able to see every state of every game. If that doesn't matter to you, then that's fine. If secrecy matters (say, a poker game,) you may need to take additional steps to make sure people can't cheat.

2) A public IP address alone only identifies a network interface. As you suggest, for a typical device, this will be the network interface of your firewall/NAT gateway. To identify a particular "service" or "application instance," you need an IP address plus a port. Thus, you need to store IP address and port in the database. Then you need to make sure that that port stays the same. You do this by keeping the connection alive; for TCP by not closing it, and for UDP by keeping a stream of messages going.

But a public IP + port just identifies a connection, not a player. If player 3 wants to challenge some other player, you really need a unique player ID. Then perhaps you can have a look-up from player ID to current connection. However, connections, in turn, only work client-to-server, unless you also establish peer-to-peer connections, and to establish peer-to-peer connections, you need an introducer to do NAT punch-through. You can either roll this on your own using UDP sockets and some central server as the coordinator/matchmaker (this doesn't seem to be built into Firebase,) or you can use existing STUN/TURN servers and infrastructure to set this up.

In general, "serverless" platforms like Firebase often end up being a poor match for interactive multiplayer games on the internet, because games often have unique requirements. Sometimes, you can use them, but you will pay a higher overhead than you'd pay for a custom game-specific solution. Sometimes, that overhead is OK, and othertimes, you really do need to develop your own infrastructure from lower-level primitives.