A resposta parece ser adicionar um repositório de terceiros:
Novo método:
sudo add-apt-repository ppa:jonathonf/python-2.7
sudo apt-get update
sudo apt-get install python2.7
python --version
Método antigo:
O antigo repositório de deadsnakes não está mais disponível:
sudo add-apt-repository ppa:fkrull/deadsnakes-python2.7
sudo apt-get update
sudo apt-get install python2.7
python --version