The simplest 2600 games were just 2k in size not 4k. Combat for example, is a 2k rom.
If you want to increase your chances of finding something but still generating a "complete" rom, then limit the size to 2k.
If 256 bytes is enough to code a demo...
https://www.youtube.com/watch?v=wlW84fEHngM
https://www.youtube.com/watch?v=O-WjF_dxdHM
I'd say gentlemen (m/f) start your random number generators
SectorLisp:
https://justine.lol/sectorlisp2/
Ok, Lisp and Forth can bootstrap themselves from a small core, but still...