As. Taaz sais, you must open port in router and redirect to your local ip. You just need to do this, where connection should be established (ex: where server resides not clients)
But this problem, you have it with Lazarus and whatever language you use to develop your application. It's not a Lazarus problem, it's a "network" problem.
You can avoid NAT, using an intermediate application. Just like Teamviewer for example does. Teamviewer don't need NAT because all communications first goes by its servers.
For this, you need a "bridge" app, communicating with all clients. I mean. Imagine I want to connect to your server. Your server is connected to the bridge, waiting commands. My client connect to the "bridge app", and I tell it, I want to connect to your server. The "bridge " then pass communications to your server, and send and receive all communications. This way, you don't need to do UPNP, NAT and so on, but needs a public server for communication between clients purposes .
I hope I explained correctly.
EDITES:::
If i reconfigure my ports and use my machine as a server, the clients will need to reconfigure their router too?
No. You just need to reconfigure router where connection "destination" needs to be established. Where server is.
When you try to send a communication on a internet IP, normally you find a router. What NAT does, is to tell router what to do with the packets received under some ports. If this is not configured routers don't know what to do with this information because you can have multiple clients connected to a router, and router can't send all this information to all clients. With NAT you say to router.."hey, communication from port 2345 should go to local ip 192.168.1.3".