Since it's essentially running on a custom VCR, couldn't you put the actual game on the VHS tape? EG put a series of QR codes as frames that store the binary executable data (You could do something more clever but you get the concept). Video is gigantic, filesize-wise, and I'm sure you could store the data for DOOM in the same space.

If you wanted it to still play normally in a standard VCR (like it plays a recording of gameplay in a normal VCR, but loads the actual game in the custom vcr), you could store the data in the parts of the signal outside the normally rendered frame, like how captions are stored off the bottom of the screen. There's quite a few lines there that could be taken advantage of