Con el Avidemux2:
-Abres el vídeo
-Le das a V Codec y eliges por ejemplo Xvid
-Le das a A Codec y eliges el codec de audio que quieras
-Le das a V Process
-Le das a A Process (si vas a recomprimir el audio, si no pues no le des)
-Menu file->save->Save video...
Donde eliges el codec de vídeo y audio puedes también darle a "configure codec" para cambiar opciones de compresión.
Con mencoder:
mencoder video.mpg -o video.avi -ovc lavc -oac mp3lame