O que você precisa fazer é, no sistema offline, executar
sudo apt-get install -s ubuntu-restricted-extras
Isto irá não instalar (é apenas uma simulação), mas mostrará os pacotes de dependências que você precisa. No meu caso, a saída é
davide@brenna:~$ sudo apt-get install -s ubuntu-restricted-extras
[sudo] password for davide:
Lettura elenco dei pacchetti... Fatto
Generazione albero delle dipendenze
Lettura informazioni sullo stato... Fatto
I seguenti pacchetti saranno inoltre installati:
chromium-codecs-ffmpeg-extra flashplugin-installer gstreamer1.0-fluendo-mp3
libavcodec-extra libavcodec-extra-56 ubuntu-restricted-addons
[...]
Portanto, preciso instalar também chromium-codecs-ffmpeg-extra flashplugin-installer gstreamer1.0-fluendo-mp3 libavcodec-extra libavcodec-extra-56 ubuntu-restricted-addons para que funcione.
Procure por estes pacotes aqui - i386 ou amd64 depende se você instalou uma distribuição de 32 bits ou de 64 bits - baixe e instale -los à mão.