O que faz tudo e um pouco mais é o FFmpeg, creio que o melhor programa no gênero.
É por linha de comando, se aprender a usar, o que não é tão difícil assim ao menos para o básico, é o melhor de todos.
Se tiver dificuldade com a linha de comando, na Central de Programas do Ubuntu há um front-end, isto é, uma interface gráfica para o FFmpeg que é o WinFF.