O FFmpeg deve fazer o truque no Linux:
ffmpeg -metadata title="TITLE" -metadata artist="ARTIST" -metadata date=DATE -metadata genre="GENRE" -metadata comment="COMMENT" -acodec copy -vcodec copy -i old.avi new.avi
Encontrei isso em um tópico em um fórum de discussão do Arch Linux .
UPDATE: devo salientar que esta não é uma solução perfeita, já que você não está realmente adicionando ou editando metadados ao arquivo existente, mas sim duplicando o arquivo com os metadados especificados. Não é uma "solução" ideal, mas é o melhor que encontrei até agora.