Aparentemente, não existe uma versão empacotada de mitmproxy disponível para o Ubuntu-14.04 em uma versão mais ou menos atual.
Eu consegui instalá-lo manualmente seguindo a documentação do github . Foi um pouco doloroso, já que eu tive que instalar e instalar muitas coisas em Python. mas finalmente consegui um mitmproxy rodando na versão 0.18 . Como esperado, não mostra os mesmos problemas que a versão antiga que é empacotada para o Ubuntu-14.04 (versão 0.9.2 ).
Eu só postei isso para não deixar essa pergunta sem resposta, embora isso não responda à pergunta original para um pacote menos desatualizado de mitmproxy .