Re-implementing HTTP over proxy using a raw SSL socket seems like a lot of work. (personally I would try to get the service to use SSH tunneling, but maybe you don't have control over that)

I would guess someone already did HTTP proxy in Perl before, and a little googling proved fruitful:

Stack Overflow: Perl HTTPS over proxy using LWP::UserAgent

Does that do what you need?