As outras respostas apenas abordam as dependências para fazer com que os erros que você mencionou desapareçam. A lista de todas as dependências necessárias é realmente muito mais longa.
Você pode instalá-los todos com:
sudo apt-get install python-pip python-dev libffi-dev libssl-dev libxml2-dev libxslt1-dev libjpeg8-dev zlib1g-dev
Você pode instalar mitmproxy
:
sudo pip install mitmproxy
E execute:
mitmproxy
Fonte: a documentação