Hardware composite video overlay
The normal solution is a "genlock": sync your system to the incoming video, then selectively replace bits of it.

You will need:


sync separation (single chip solution)
fast analogue switch between your signal and theirs
recombine the signals (or just output them as S-Video)


Edit: or there's almost certainly a single chip solution for the whole thing. Here's a mono version. https://www.sparkfun.com/products/retired/9168