Ogni volta che mi serve aggiungere una traccia audio .mp3 ad un file .avi (sostituendo quella che c'è già) perdo un sacco di tempo a cercare su Internet. Sembra che non molti abbiano questo stesso problema su Linux ma lo segno lo stesso qui in modo da ricordarlo:
mencoder original.avi -o new.avi -ovc copy -oac copy -audiofile audio.mp3
Altri consigli utili su come usare opportunamente mencoder si possono trovare qui.