How can I run two Arduinos in sync for video generation? I was thinking about building a video circuit that uses two Arduinos (maybe more) to generate video using NTSC and the AD725.  Although, VGA might be nice if possible.

Anyway, the idea is to use one Arduino as the background layer and the other one as the sprite layer (overlay).

Then, instead of masking the sprite data and having more cpu time, I was thinking of running the signals through a mux.  So that when drawing background data and no sprites (per scanline) then pipe the signal to the AD725.  But when there is a sprite mid-line, then the >0v signal of the sprite Arduino would cause the mux to pipe its contents through to the AD725.

Or, something similar.

I believe many arcade boards from the 80's did this.  Many of them had entire "sprite boards" attached and the signals would mix.  Each layer would have it's own RAM and not be aware of the other layer.

But to do this, I would have to keep the Arduinos sync'd perfectly.

So that's my question.  How I can do this?  

Oh, my Arduino of choice in the beginning would be the UNO but I have others (DUE, Teensy3.1, etc.) if that would be a better fit.

Thanks.
I would take a look at MREtv which seems to promise all that you want to do, with just one arduino. This might not be the answer you're looking for, but getting threads to sync is a pain in the rear end, see this for explanation of why threads are a pain.

Now back on topic, it seems like MRETV might off what you want to do, and it can do some pretty impressive things from what I read in the arduino. You might need to modify the library a bit, but it offers already implemented encoding, so that is a plus.

http://www.instructables.com/id/MRETV-Video-Stereo-Sound-and-much-more-from-a-s/