Existe uma corrupção no arquivo que está tentando instalar, você pode dizer por causa desse erro: lzma error: compressed data is corrupt
Isso pode ser causado por uma conexão incorreta, download retomado, arquivo incorreto, corrupção de disco ou falhas, etc.
O problema é que ele manteve o arquivo e, em vez de fazer o download de uma nova cópia, está tentando instalar a versão em cache.
Dothis:
cd /var/cache/apt/archives
sudo rm libavformat-ffmpeg56_7%3a2.8.8-0ubuntu0.16.04.1_amd64.deb
sudo apt-get update
sudo apt-get install vlc
Como alternativa, você pode fazer um sudo apt-get autoclean
para limpar seus pacotes em cache.
Isso deve excluir a versão que está causando problemas e permitir que o seu computador faça o download de uma nova cópia.