The starting point should be the simpler solution. What's the argument for introducing NAT? Why is the firewall (that you need anyways) insufficient?