Thanks to this hint Macosxhints.com, I’ve finally found a way to get programs that don’t support proxy authentication (like Ruby’s Gem, Perl’s CPAN, etc) to work behind the authenticating proxy at work. The article is for MacosX, but it works just as well under Linux. The short summary is that you can install a local Squid proxy, then configure Squid to forward all request to the upstream proxy. Squid handles the authentication, just configure your applications to use the local Squid proxy (without authentication). I tried it this evening with Gem, and it works great!
One caveat: This works with proxies that use HTTP basic authentication, I don’t think it’ll work with NTLM authentication (MS-Proxy).