Você pode usar Proxychains para isso.
Primeiro, instale os proxychains usando o comando:
$ apt-get install proxychains
Em seguida, defina suas configurações de proxy no arquivo /etc/proxychains.conf
.
Adicione finalmente estas linhas para o proxy HTTP e HTTPS.
http proxy-ip proxy-port username password
https proxy-ip proxy-port username password
Agora você pode fazer o telnet usando o seguinte comando:
$ proxychains telnet www.google.com 80