Can you rate-limit on your proxy?
If not, can you specify that Customer A goes through your proxy and appears to be coming from IP address "A", while Customer B goes through and appears to be coming from IP address "B"? Because then you can either implement your own rate-limiting on a device that you install between the proxy and the upstream ISP's customer premises equipment. And have it restrict throughput by using access control lists to match against those IP addresses. Or maybe you can get the upstream ISP to do the rate-limiting at their end.
The only way you're going to conserve Internet bandwidth AND restrict customers to contracted Internet access rates with the equipment you've described is to do it on the proxy or upstream from it.
Is your proxy transparent to the end clients? Or does it do NAT-like address translation?
If your proxy does caching, maybe you should just let it do its best-effort at getting the pages and then rate-limit the customers on the downstream side.
Which is more important: rate-limiting the customers, or conserving Internet bandwidth? If rate-limiting the customers is, then downstream from the proxy is fine. If conserving Internet bandwidth is, and your proxy can't segregate its upstream requests corresponding to each of your cusomters, then you are stuck with generally restricting the whole proxy system's access.
Can you tell us a little more about the equipment in use in front of, and behind the, proxy? Switches, routers, hubs.
EDITED TO ADD: If you can uniquely ID each customer's Internet-bound traffic as it leaves the proxy, then you should probably rate-limit both upstream and downstream from your proxy.
Hope this helps.
