Iptables – Local transparent proxy

Redirecting traffic of all protocols to proxy server will not work especially for udp-based protocols.

If you want to implement traffic shapping to control bandwidth, you use 'tc'.

For logging, you can use iptables logging for simple things like initiating and terminating connection (matching specific rules). For more detailed logging, this requires speciallized software for packet inspection.

The only thing I can think of is some form of a tunnel. You simply have to route that port 80 traffic, which will have random global destination IP addresses, to your cloud proxy. This is impossible to do without some sort of support in your routing infrastructure.

You'd probably want an IPsec tunnel between your network and the cloud instance for security anyway. If your current router(s) don't support such features, I would suggest expermienting with Vyatta Core, pointing some test workstations at the Vyatta router as their default gateway. They Vyatta would then be configured to redirect all public-bound TCP-port-80 traffic through an IPsec tunnel (or even GRE or IP-in-IP if you don't care about security) that terminates on the cloud instance.

Note whenever tunnels are involved, you will have MTU issues, so you should make sure you are not blocking ICMP packet too big messages in any firewall (even local to the workstation) and you can potentially rewrite the TCP max segment size in TCP handshake packets seen by the Vyatta.

Honestly, proxy-auto-config is going to be much easier to deal with. You can even enforce proxy configuration for IE and Google Chrome via Group Policy if you have an ACtive Directory Domain, and use proxy autoconfig for visitors/Macs/Linux/Firefox users.