For a logo - large or small
Maybe try Avidemux, versions for Linux (see your repo) or windows see
http://www.videohelp.com/tools/AviDemuxA few caveats,
No transparency, Your example seems to have transparency. If the logo is over a static part of the video, you can adjust your image and duplicate that section of the video.
If you want to add to just part of a video, you will have to split the video & rejoin after adding the logo.
Lots and lots of tutorials & demos out there, this is my quick demo (3 mins)
http://youtu.be/7_wfyF3joJIA better bet might be a subtitle, You can use Avidemux and it is not too difficult.
Caveats, although you can choose a font, colour & vertical position you are stuck with the text centered in the frame.
my example (3 mins)
http://youtu.be/2tluaNV_j8oFurther than that (and free) you might have to look at Avisynth ( a frame server) in conjunction with Avidemux, but then it can get complicated.