Nenhuma das respostas existentes funcionou para mim no Ubuntu Server 16.04, então executei:
sudo apt-get install libmysqlclient-dev
sudo -H pip3 install mysqlclient
O primeiro comando me dá a configuração do mysql necessária para o segundo comando.
