While creating NAT Gateway an Elastic IP Address is created in AWS. The AWS documentation (1) also mentions the same. Why is an Elastic IP Address required for NAT Gateway?
The EIP requirement is rather arbitrary. Having a static IP makes coding the NAT easier (it doesn't have to check the WAN Interface for upstream address changes) but NATs that support a dynamic upstream address are very common - almost every home served by a major ISP has one. Sure, there's a risk the external address might change and break the current connections, but the ISPs know this and try hard NOT to change the address. Generally it changes only when you reboot the router, and at that point all your connections are broken anyway.
On AWS there there are many similar scenarios where you don't care if your NAT gateways external address changes, especially if your VPC does not contain any public servers. I have a lot of these, and I'm trying to run them on free accounts - it annoys me that they force me to burn through my short supply of static IPs.
As others observed this is a small expense, and AWS is still way cheaper than any other way I know to get this kind of cloud power; but that EIP is not strictly required.