How can i make a handshake between two clients using a relay server?

I think this is the key: the client initiates the connection. This way NAT is not the problem. Perhaps you can do some tests: