How do you test the rules of a new firewall before pushing into production?

In some places, we don't always have the luxury of a full test environment. In those cases, how do you test a new firewall to ensure all of the holes are poked accordingly before moving to production? I've used nmap with an alphabet of strings behind it, tcpdump stuff, but is there an easier or different way to do it?

For those of you who have to document something before it hits production, how do you do it? Is it a manual process to make the data look good or is there a tool you use?

I'm just curious to see how other people test/store/present the process of implementing a new firewall/router in an environment where disruption is crippling.

Everyone has a test environment, not everyone has a separate production environment