I would create a 1 minute video of the water mark looped with the watermark moving every 20 seconds then use the overlay filter to overlay that video looped onto the original video.
Here is image looping:
http://ffmpeg.org/trac/ffmpeg/wiki/Create%20a%20video%20slideshow%20from%20images
And Watermarking:
http://www.idude.net/index.php/how-to-watermark-a-video-using-ffmpeg/
You could even repeat the process for the watermark video until it has the same length as the original video. I haven't tested my theory, but you could let us know if it works.
edit, I went home and tested my theory, here's a Windows batch file:
setlocal
rem create blank movie
rem I created 4 transparent PNG the same size as my final movie using FotografixPortable
rem after many failures with MSPaint... I should have known...
rem add water mark to blank movie (bottom right)
ffmpeg -loop 1 -i wm1.png -t 20 -vcodec png -pix_fmt rgba out-wm1.mov
rem add water mark to blank movie (top right)
ffmpeg -loop 1 -i wm2.png -t 20 -vcodec png -pix_fmt rgba out-wm2.mov
rem add water mark to blank movie (bottom left)
ffmpeg -loop 1 -i wm3.png -t 20 -vcodec png -pix_fmt rgba out-wm3.mov
rem add water mark to blank movie (top left)
ffmpeg -loop 1 -i wm4.png -t 20 -vcodec png -pix_fmt rgba out-wm4.mov
rem put (concat) them all together into one video
rem I use filter_complex because we need to maintain the transparency in the video
ffmpeg -i out-wm1.mov -i out-wm2.mov -i out-wm3.mov -i out-wm4.mov -filter_complex "[0:0] [1:0] [2:0] [3:0] concat=n=4:v=1:a=0 [v]" -map "[v]" -y -vcodec png -pix_fmt rgba -q 0 all-wm.mov
rem finally overlay the 1:20 watermark video onto the original movie
ffmpeg -i "Ted (2012) Unrated.mkv" -i all-wm.mov -filter_complex overlay -shortest -y -q 0 ted.avi
Granted, it's not "random" but you can make your overlay movie any length of patterns and individual time stamps to make it appear random in the final output.