@Tim Sullivan, the standard VHS has a "helical scan" where the head is on a mechanical drum spinning at an angle to the tape. The spinning drum has to be synchronized to the video scan, on in your case to the Arduino. Fine tuning the synchronization of this mechanical drum is what the VHS "tracking" control does.
As @cyberteque points out that an analog cassette tape with its stationary head would be much less complicated. There are also VHS recorders that have non-spinning heads, they cannot record video, but in a 911 center a recorder is used that has 10 or 20 channel stationary head to record audio phone calls and voice radio calls on regular VHS cassettes. They can fit 20 audio lines x 24 hours on one cassette. If you want to record data on a VHS cassette it would be much easier to start with one of these rather than a regular VCR.
They are amazingly expensive new, but now that call centers are changing over to digital recording on hard disk, I bet these VHS tape units show up cheap on surplus and even free if you look in the right dumpster.
A 20 track VHS unit from a call center could record 16 parallel bits, plus a data clock and 3 error correction bits. Recording 16 bit data at 2kHz would give a capacity of about 345 GBytes per cassette.
Is this mountain worth climbing? Its a lot easier than conquering the regular VCR recorder, but alas price of disk and solid state memory continues to plummet, so success here would practically be worth just a tee shirt and bragging rights.