I agree with davr. The cheapest alternative is to get your own dedicated server.
Take a look at this for instance:
http://www.server4you.net/root-server/server-details.php?products=5
Hosting in Germany is relatively cheap (compared to US prices). This is a dedicated Server with 2x 1TB HDD, QuadCore CPU and 8GB Ram. Traffic is 100Mbit/s flat. All in all 99 EUR per Month (135 USD).
Most German Datacenters got direct peerings at DECIX, AMS-IX and/or LINX (which by size are the three largest Internet Exchange Points worldwide). So if your service doesn't mind 150-300ms latency you usually get the full 100 Mbit/s throughput even on the Westcoast.
So, maybe get a couple of these and you should be fine.
Though it should be mentioned that this can not replace a proper CDN. But since you're asking for an alternative to S3, not CloudFront I guess this is understood.
Another alternative would be this offer
http://www.hetzner.de/en/hosting/produktmatrix/rootserver-produktmatrix/
Although traffic is flat too, they shape you from 100 Mbit/s down to 10 Mbit/s if you transfer more than 2TB/Month or alternatively charge 15 EUR for each TB over 2TB. So all in all you'd be around 99 EUR for the Server plus 345 EUR for the 23TB additional traffic.