Nat is the only solution.
To access the NAT`ed systems You can always forward one of non-standard port to the nated system as ssh for example.
You can read more here: http://blog.softlayer.com/2011/iptables-tips-and-tricks-port-redirection
This will work on any host supporting standard...