Você pode corrigir o problema se tiver acesso a algum VPS do Ubuntu que está funcionando bem:
apt download python2.7-minimal libpython2.7-stdlib python2.7
Então você tem que copiar os arquivos essenciais para o seu próprio sistema com:
sudo scp you@yourserver:/usr/lib/python2.7/*.py /usr/lib/python2.7/
sudo scp -r you@yourserver:/usr/lib/python2.7/plat-x86_64-linux-gnu /usr/lib/python2.7/
sudo scp -r you@yourserver:/usr/lib/python2.7/logging /usr/lib/python2.7/
sudo scp -r you@yourserver:/usr/lib/python2.7/encodings /usr/lib/python2.7/
Então você deve usar o dpkg para instalar o python:
sudo dpkg -i python2.7-minimal_2.7.12-1ubuntu0~16.04.2_amd64.deb libpython2.7-stdlib_2.7.12-1ubuntu0~16.04.2_amd64.deb python2.7_2.7.12-1ubuntu0~16.04.2_amd64.deb
Então você deve deixar o apt cuidar de si mesmo:
sudo apt-get install -f
Então você pode verificar se o apt está funcionando bem com:
sudo apt upgrade