Im looking for a service that would allow me to NAT HTTP traffic through multiple outbound IP address. I've seen services taht can offer ~100 different public IP addresses, and let users change it every minutes for example. Can you suggest one such provider?
SnapOverflow
Why not just setup 10 Amazon EC2 micro instances running Linux/Squid and use them as a proxy?
To get a decent variant of IP addresses, you would need to terminate them fairly often and even that isn't a guarantee that they'll be different each time, but if you vary the availability zones, for each instance, you should be able to rotate IP addresses fairly well.
The nice thing about Amazon is that the ec2-tools are very robust/scriptable, so if this pilot works well for you, you could partially/fully automate the process using the response code (403 forbidden I'm assuming) as your condition (say by syslog'ing Squid to your "proxy master"), which would then fire off a new EC2 instance, record the IP, and write it to your proxy .PAC file/URL (that would be configured in your browser).
All this is just back-of-the-napkin "architecture" talk here, but I think the core notion of EC2 instance rotation is sound.