Um dos métodos de instalação de um software que não está no repositório padrão do Ubuntu, mas através do apt-get, é usar o Personal Package Archive (ppa). Todos os ppa's estão hospedados no link . Na busca, descobri que um dos ppa tem a versão do vlc que você precisa (vlc-2.0.4). link .
Isso tem todas as dependências que o vlc-2.0.4 precisa.
Adicione este ppa ao seu sistema assim:
sudo add-apt-repository ppa:n-muench/vlc2
Em seguida, atualize suas fontes por:
sudo apt-get update
Em seguida, instale novamente:
sudo apt-get install vlc
Isso deve ser feito. Eu tentei e funciona. Você pode instalar a partir de outro ppa também, mas certifique-se de que ele construa com sucesso, verificando no lado direito da página principal do ppa.