Identify reverse proxies using tools like lft, osstmm-afd, or w3af. Nmap has a few NSE scripts for detecting reverse proxies, but some have mixed reliability, such as http-traceroute.
Perform packet creation activities from the nodes past the proxies/NATs using techniques such the ones in nsping, ntp monlist, or 0trace.
If an encrypted service is available on the far-end, such as SSL/TLS or IPSec -- use it to tunnel your traffic. Try to create your own tunneling service if one does not already exist. If no encrypted services exist and you can't create them, then utilize a tool such as sniffjoke or find a hole with FWTester, Pytbull, or Scapy.
NAT also allows UDP and TCP hole punching to occur, which is how Skype gets around NAT. A multitude of other ways exist, such as NAT Pinning, DNS Pinning, and client-side attacks such as the ones available in SET (with or without browser_autopwn from the Metasploit Framework), BeEF, XSSer, XSSF, Yokoso, et al.
Most of the above depend on your entry points and capabilities to pivot from them.