ryangodammit:
Any other suggestions of where to start?
I think there is a chip that will impose text onto video, I think one of my amplifiers has that for when you enter setup mode. I'm guessing it synchronizes with the incoming video and then just forces it to white (for the duration of a pixel) when text needs to be displayed.
However that is hardly an Arduino, unless the Arduino tells the chip what to display (which could well be a use for it).