Amazon EC2 - need to change IP address without downtime

Yes there is! Embrace the power of DNS eventual consistency.

1. Set up an ELB, point it at your instance.
2. Update the A record for your public instance with a CNAME for the ELB.
3. Wait a week.
4. Associate an Elastic-IP with the instance.
5. Update the CNAME record for your app with a new A record for the EIP.
6. Wait a week.
7. Turn off the ELB.

For the two weeks of waiting site will likely get hits on both the old and new IP addresses. You might not be able to tell, but as both are still reachable you can manage this change pretty quickly.

Another option is to create an ENI and attach an EIP to it. Then attach the ENI to your instance and change the DNS entry.