After toying with the idea during most of the holidays, and going through various class hierarchies and implementation scenarios, I finaly managed to have a working implementation of Net::Proxy. (As you'll see, it's not related to HTTP::Proxy, except for the name similarity.)
Net::Proxy introduce the concept of connectors (implemented as Net::Proxy::Connector objects). A Net::Proxy object is made of an in connector waiting for incoming connections on the proxy and an out connector that contacts a remote host. The proxy passes data back and forth between the sockets managed by the connectors.
These connectors let me abstract various encapsulation protocols on top of regular sockets. The first one is the classic HTTP CONNECT, already implemented in my connect-tunnel script (which I've rewritten using Net::Proxy and included in the distribution). Other connectors will follow.
As an added bonus, this all works perfectly under Win32. And the test suite covers about 93% of the code!