No meu sistema Debian (unstable), o libssl1.0.0 também ficou indisponível, e eu não consegui pegar uma cópia dele como sugerido nas respostas anteriores.
Mas eu consegui corrigir o pacote para exigir libssl1.0.2, o que percebi que estava disponível para mim, e o Skype funcionou muito bem.
Este é o meu deb de patches: link
Você pode fazer isso sozinho assim:
# This will create a skype/ directory.
$ dpkg-deb -R skype-install.deb skype
Edite skype/DEBIAN/control
usando seu editor de texto preferido e substitua libssl1.0.0
por libssl1.0.2
(ou versão similar disponível no gerenciador de pacotes; mas, claro, se a versão for muito diferente, provavelmente não funcionará).
# This will create and install your patched package.
$ dpkg-deb -b skype skype/
$ sudo gdebi '<path to generated deb>'
Espero que ajude.