I was thinking about time flow. The levels of the monsters wouldn't be influenced by the progression in the plot, but by the time that has passed since the beginning of the story.
If we imagine, for example, a calendar system that would keep track of in-game days (or any other in-game time unit), it should be possible. All characters and foes start at a basic level, and grow stronger as time passes. If the player explores dungeon A before dungeon B, monsters in dungeon B will be stronger than those in dungeon A. If, on the contrary, the player chooses dungeon B first, then monsters in dungeon A will be stronger than those in dungeon B. They will grow in strength as time passes. We could even take advantage of the fact that in most RPGs, monsters are recycled as stronger (and differently colored) versions of themselves later in the game: the monsters could evolve at certain levels, and gain new abilities that would give a fairly balanced challenge to the party. Also, some monsters - like optional bosses - could have a fixed level.
The main difficulty that I see here consists in the elaboration of puzzles. If the game is puzzle-heavy, especially in the "dungeon" areas, the puzzles need to be solvable at any point of the game. This means that puzzles based on tools - like in Lufia or Wild Arms - are rather out of the question, unless all the tools are available from the start. Of course, this aspect could instead be implemented as optional content: no tool that isn't available from the start is necessary to finish the main adventure, but treasures and such can be discovered only with the appropriate stuff on hand (I recently finished Wild Arms 5, the game is LITTERED with "go back" dungeons ^^; ).
But the question of difficulty remains: how to increase the difficulty of the puzzles as the player progresses in the game? I was thinking that maybe a general difficulty setting could work (the same difficulty for all the puzzles, the setting being chosen at the beginning of the game), but that would be quite complex to implement.
This still needs a lot of thought. I'm sure we can come up with lots of other flaws in that idea. :)