I hadn.FN"t really thought of making it executable$B!D(B I think thereN"s a magic cookie at the beginning of a ZIP file so a hashbang might not work if the archive were intended to be spec-compliant.

No, the magic cookie (PK\005\006) is at the _end_. The central directory and file entries also have magic cookies (PK\001\002 and PK\003\004 respectively), but those don't have to be at any specific position but are pointed out as file offsets rooted in the PK\005\006 header at offset file_size-22.

AFAICR it was standard practice to make self-extracting ZIP:s on MS-DOS by just cramming an MZ binary before the archive (and adjusting the offsets accordingly).

It should be pretty easy to just put something at the start if creating the archive by hand like Filesystem.Zip is doing.