Was there no way to put RAM in the cartridges of those things?
I think you can do it, though, and have a cool game, but the monsters won't be able to move. :3 And they would be "fresh" again if you ran away and then encountered them again a short time later.
Let's see.... 2 bytes for player's x/y position. If you use a fixed "equipment" list (like in Lawrence's DND), where you have things like "weapon", "armor", "cloak", "boots", "ring", etc, where each "equipment" is just tracked by a "plus", you could get away with a nibble for each item of inventory. Assuming 16 inventory items, that'd be 8 bytes. A byte to store the seed for the level so you can restart the prng. Then maybe.... 16 monsters and 16 loots, as bitfields, that's 4 bytes. That's, what, 15 bytes? Still 11 bytes of ram left for ZP scratch area. Oh, I guess you'd need at least a nibble for the dungeon level, and 6 nibbles for stats (you can fit the 3d6 range into 4 bits if you store the stats as S-3 instead of just S, so there's 3.5 more bytes. Still........
Then just loop through the prng to find values for different parts of the level. The level layout could be generated by the first N bytes returned by the prng. Monsters N+1...n+16, etc etc. Slow, but......
Or you could partition the random number space into "blocks". If your blocks were say, 32 bits wide, you could generate a sequence of random numbers off the level seed up to the number of the block you wanted to access (which you could quickly calculate with a bit shift if the block size was a power of 2). Then reseed the prng with the random number you just got out of it, and generate another sequence up to the byte within the block that you wanted. That'd be much faster than looping through the whole shebang with just one seed....
If you can pull it off, I for one will think it's awesome, given the hardware it is running on!!! Hard to write, without having a stack to call procedures!