Você mencionou ter tentado a maioria dos cli's para resolver problemas do apt-get. Você pode tentar primeiro:
$ sudo apt-get dist-upgrade
Depois disso, tente pensar na sua lista novamente com os seguintes:
$ sudo apt-get autoremove
$ sudo apt-get --purge remove && sudo apt-get autoclean
$ sudo apt-get -f install
$ sudo apt-get update
$ sudo apt-get upgrade && sudo apt-get dist-upgrade
$ sudo dpkg-reconfigure -a
$ sudo dpkg --configure -a
$ sudo apt remove --purge [problem package]
O último comando é o nome do (s) pacote (s) do problema que foram processados para causar o erro. Substitua os parênteses e o comando pelo nome do pacote do problema. Se for mais de um, remova cada um deles.
Esses comandos (todos eles) sempre resolveram meus problemas com pacotes quebrados. Há ocasiões em que preciso repetir a lista de comandos mais de uma vez para esclarecer tudo.