The thing about the chest rarity is that there can only be a maximum of 256 chests among all the overworld maps. This is a technical limitation of the rom that is difficult to avoid, especially when I'm trying to use as much of the map space as I feasibly can.
An in-game dungeon randomizer was an idea I toyed with for Chrono Trigger. While I would face many of the same technical limitations as yourself, it was technically feasible that I could create a random 'fake' chest. It wouldn't be automatic, and there would be little to no long-term tracking of it. Would work something like:
- Paint a tile with a closed chest.
- Make the tile solid.
- Attach an interaction event to the tile.
- Paint tile with open chest.
- Play treasure sound.
- Give item to player.
- Display dialog.
- Turn off object.
But then, Chrono Trigger is capable of some pretty advanced stuff, like self-modifying code. I admit I don't know anything about FF4's event commands or memory usage, so this might be two or three orders of magnitude impossible.