I think if I was going to try this with a (working) VCR, I would do something fairly "unorthodox" - I would purchase this shield (or the chip) - which was recently released:
I would hook its input to the VCR's output, and its output to the VCR's input. Then I would hook up the play, record, rewind, fast-forward, and eject buttons to the Arduino.
Write the code to use the TVOut library to output checkerboard patterns encoding the data; then use routines (on playback) to read the data (similar to the blob tracking demo). IIRC, this is similar to how various "backup" to VCR systems back in the day worked (although some, I recall, used the audio tracks instead). You could also possibly just record black->white transistions in the video area using the TVOut library, and then read the transitions in some other manner via an analog input...
Ok - maybe its a bit "pie-in-the-sky", but it would probably be the easiest and most reliable way to get something like this working (well, short of just recording audio like the old-school cassette tape systems).