Or rephrased its not possible to implement "working" NAT without a stateful firewall, but the lack of NAT doesn't imply its impossible to deploy a stateful firewall.

(It would be interesting to research where this "can't have a stateful FW without NAT" meme came from. It is VERY popular among everyone but network guys)