I used to back up harddrives, 5M, back in my Apple 2 days.
The thing that will be hardest to overcome is your common or garden variety VHS deck is pretty sloppy timing wise.
The horizontal lock on ananlog TV is pretty tolerant of these variations, but the Corvus harddrive backup unit had real problems coping.
We ended up having to buy studio or broadcast quality decks for our customers.
When Sony first released the F1 PCM recorder that was a companion unit to their first model of CD player, you had to use a particular model of VCR.
It was all interconected by incredibly expensive 100 way cables.
Each line of video is 63.5 uS, followed by an 8 uS horizontal sync pulse.
There are 2 fields of 312.5 lines, at the end of each field is an 11uS verticle sync pulse.
Then a 22 uS vertical retrace period.
If you only stored say, 100 bytes/line, which would give you about 3k bytes/field.
With a 15625kHz line rate, @100 byte/line, you'd have to clock data out @1562.5kHz.
Straight up it would need a Mega, just for the buffer.
At the end of the day it seems like a lot of hassle just for the intelectual exercise!
You could go really retro and build an audio cassette interface!
It would be a lot less hassle and you could use it for other things, like a laser data link or go nuts and communicate between two Arduinos with tin cans connected by taught string.
Which I have done! It was pretty funny!