https://addons.heroku.com/proximo does what's needed, but at a serious price for high volume.
This was one of the reasons we handled server deployments ourselves for our startup. The cloud version of our app runs in production on AWS in a VPC so all outbound traffic is NATed through a single public IP. With reserved instances it costs about $22/mo for the NAT gateway and setup was pretty straightforward.
I've considered doing this myself so I'm curious: are you getting good network performance through the NAT gateway? What instance type are you using?
At the moment we're using an m1.small for the NAT itself though if you have perf issues you can bump that up as well. I would guess a c1.medium would be more appropriate though as I said we haven't had any issues so haven't considered changing anything yet.
Here's a speed test through from a m1.small through the NAT (27.5 MB/s):
$ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 500M 100 500M 0 0 27.5M 0 0:00:18 0:00:18 --:--:-- 29.2M
Here's a speed test from a m1.small vanilla EC2 instance outside the NAT (38.2 MB/s): $ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 500M 100 500M 0 0 38.2M 0 0:00:13 0:00:13 --:--:-- 34.1Mhttp://aws.typepad.com/aws/2013/03/amazon-ec2-update-virtual...
Meanwhile, there is an add-on that does exactly this: https://addons.heroku.com/proximo
I'm not sure how economical it is to provide this for the free tier though I think a paid option would be viable. AWS charges $3.60/IP/month so it's not that expensive and I'm sure there are plenty of folks who would pay $10, $20, or even $50/month for a unique outbound address.