I like the concept of a having a totally different weather context in the game. A few comments on your "to do" list.
- New map layouts are always a big plus for me, so new palaces and new caves equals thumbs up. The tile layout system is a bit clunky with editors because of the way the "writing head" moves, relative to the last object placed. This is of course a tradeoff to save space, but banks 1 and 2, which are the two Overworld banks, have plenty of unused space to play with. Bank 1 has a total of 0x186D free bytes, 6253 decimal, which represents 38% of the bank total space. Bank 2 has 0x17EF unused bytes, 6127 decimal, which is 37% of the total. So, go crazy with the maps details. Creating new tile objects is possible, although you need to program them by hand.
The actual limitation is more about the number of areas available. There is a maximum of 63 per region. However, you can use the same area data for more than one place. The original game has this in several places. For example, the cave that you go through to get to the first palace is used many times. The terrain data is the same, but each individual place takes a slot in the 63 available. Areas can be 1 to 4 screens wide, and you can use multiple screens of the same area for different smalls places. Also, you have to reserve 14 areas for random battles. There are 7 possible terrains where you can hit a Demon: desert, grass, forest, swamp, graveyard, road and lava. Each type has weak and strong variations. If you forfeit any of these types of terrain battles, you win back as many areas for something else. You also have to consider Towns and Palaces, which all take slots in the list.
- Having small variations on bosses would be very interesting. I can help with ASM, as I did quite a few things with regular enemies. Sometimes, it's just a few variables tweaks to make an enemy easier or harder, or less predictable. With simple ASM, we can randomize some behaviors. You can change projectile types with a few bytes.
- The new map idea is ambitious, but having 5 will certainly require ROM expansion. Not impossible, but it's quite an undertaking, as you need to consider many types of data, and most importantly, saving the data to Cartridge RAM. The game has a few quirks about how regions are loaded relative to what spot in the map you walk on. The original game has room and code for 4 distinct Overworlds, but 2 of them, Death Mountain and Maze Island, are perfect copies of one another. Both contain the Overworld tiles of both, Maze Island being to the far right of Death Mountain. Changing one doesn't change the other, however, some internal data is shared between the two, including the saved bytes that keep track of item taken, among other things.
- Modifying spells is also straightforward. You can change their effects, their names and the order they appear in the Pause Pane.
- Changing the starting stats, like Heart/Magic Containers, is very easy.
- Enemy HP is also easy to change, there are tables just for that. What makes it a bit limited is the graphics tiles for the visual EXP points digits that float after killing an enemy.
One suggestion I have to make the game "feel" longer would be to have palaces with no crystals, or possibly no bosses. They could be smaller than others, but still contain an interesting item, including Heart/Magic Containers. The game engine certainly permits that.