They may not require *dedicated* public IP addresses, but there still have to *be* public IP addresses available at ends A and B of the links, otherwise X cannot send reply packets back to them.
So long as A and B have public IPs which they can NAT behind, then there's no problem - they can either communicate directly, or if you want to channel the link via some other server X on the Internet you could do that easily enough with a couple of SSH tunnels back to back. Given public IPs all sorts of opportunities come to mind.
I still say however that if A and B do not have public IPs available to hide behind, then they can't communicate with *anything* across the Internet.
Yes, I totally get you. Thing is, I am looking for a way to connect to some machine which may be hidden behind some NAT/Firewall etc. from a server which has a public address.
So, the only solution that comes to mind is: That given ("hidden") machine initiates the connection to the public server/address (because it can). Next, this established session needs to be somehow used/'hijacked' to "get to" the 'hidden' server. Follow me? ;-)
Cheers Sven