Well, it won't be easy, that's for sure.
At this point, I think the following 'plan of attack' is the most realistic.
Use Component video (YPbPr) instead of analogue video (keep reading if you want to know why) and an Arduino Eye Shield as start.
The Eye Shield (and derivatives like the Video Experimenter) can only process monochrome video. That is a problem for what I want to achieve and that is why I hope the change to component video can help us out. If you read the specs of YPbPr, you'll notice that the Y signal is pretty much analog video. The Pb and Pr signals are used to add color. Once you have the Y signal and the Pb and Pr values, color determination is only basic math. One remaining problem: can I get the timings right? I think I can use the Eye Shield to process the Y signal, but I need the Pb and Pr values at the exact same time. I still have to figure out if that is possible. And off course there's the issue with the different resolutions. Will have to figure that out too :-)
I also have to figure out how the Y signal is built. I believe this site is what I'm looking for, but I'm still not sure if RS-343 is the correct standard.
More work to do...