Pois, sem internet é que não consegue mesmo instalar esse pacote...
Vai ser mais aborrecido. Tem de fazer download no do windows e passar por pen ou assim o ficheiro .deb de
http://packages.ubuntu.com/karmic/i386/ubuntu-restricted-extras/download
e escolha o mirror mais próximo. Eventualmente poderá ter de instalar as dependências constantes em
http://packages.ubuntu.com/karmic/ubuntu-restricted-extras
Para instalar o deb no ubuntu tem de copiar o deb que gravou no windows para por ex. a directoria /tmp. Depois faça
sudo dpkg -i /tmp/ubuntu-restricted-extras.deb
Com sorte fica logo tudo a funcionar e não há dependencias. Se houver terá de fazer download de todas e fazer a instalação manual.
Infelizmente não conheço modo mais simples de fazer isto, porque na verdade o que lhe falta não é o programa mas os "drivers". Imagine no windows em vez de fazer download do programa, fazer download das dll's do sistema e instalá-las manualmente... O comando que lhe dei fazia tudo isto de modo automático, assim vai ser muito mais duro.
Cumps