Sua primeira abordagem é boa, você pode adicionar mp3 em KDENLIVE ou Kino ou pode ser vários outros editores de vídeo como o pitivi. Você pode ver a lista completa aqui
Espero que você possa encontrar sua solução aqui também.
Algumas outras fontes de ajuda: