Estou procurando uma solução na qual possa adicionar marca d'água ao vídeo em questão em um determinado frame.
Existe algum utilitário / ferramenta para fazer isso?
O mencoder pode definitivamente fazê-lo, embora o pessoal que eu conheço tenha a tendência de usar um dos aplicativos gratuitos do Windows (por isso acho que você pode usar um deles no Wine)
Além disso, o bmovl deve ser capaz de fazê-lo. Confira esta discussão.
Se você quiser fazer isso programaticamente mencoder é a ferramenta para o trabalho. Você precisará de uma imagem estática (ou gerar uma programaticamente com o ImageMagic, gd, etc) e algum tempo para brincar com filtros.