O Ubuntu 14.04 também tem o arquivo lsb_release.py instalado para o Python 2.7 e o lsb_release também funciona com o python2.7. Você pode tentar fazer isso:
python2.7 /usr/bin/lsb_release
Se isso funcionar, faça um backup do arquivo /usr/bin/lsb_release e altere a primeira linha para ler:
#! /usr/bin/python2.7
(você pode experimentar com as opções -Es , eu as deixaria de fora inicialmente).
Quando puder executar apt-get novamente, reinstale o python3 e suas dependências. Você pode determinar as dependências diretas usando apt-cache depends python3 e usar apt-rdepends ou reverse-depends (ambos precisam ser instalados) para obter dependências recursivamente.