I'm imagining mainstream messaging applications on mobile phones but without centralized servers.
Somehow two phones, connected to internet over mobile network, are matched and create a connection between them. Then Phone A moves out of it's current network and it changes it's IP. Phone B's IP address is still the same so Phone A tries to create a connection. Most likely Phone B is behind a NAT, so how this connection is created? Phone A only knows Phone B's public IP and the "router" doesn't have the connection between Phone A and B in it's NAT table. So how I view it, it is not possible, but hoping for some way out.
Use IPv6 when available, it doesn't suffer from NAT.
For IPv4 the keyword you are looking for is NAT traversal, for which many approaches exist. Most require some form of rendezvous point, which can be a 3rd peer that both know about. But other approaches such as time-based coordination exist too.
NATs with endpoint independent mappings (also known as full cone NAT) require no coordination at all as long as each peer keeps the mapping open through regular pings. This is the recommended implementation for UDP CGNAT.
Some CGNAT implementations also support PCP through which you can request an explicit port mapping.