I've used cntlm to automatically add NTLM headers to https requests when ssh'ing to a particular host.
What I need to do now is to send all outbound internet traffic (80/443) from any program running on machine A through a proxy server running on machine B transparently.
Machine A and B are on different networks (over the internet)
Is this at all possible? If yes, I would appreciate a quick how-to..
http://tldp.org/HOWTO/TransparentProxy.html
This sounds like what you're asking for. No?
Note that HTTPS traffic will be a challenge to proxy without detection. The closest you're going to get is if you a) have control over machine A, and b) have control over machine B. In that case you can provide a wildcard certificate from B, and configure A to trust it.