I do think Zelda games should have difficulty levels... at least now. If they did, they could easily appeal to newer, less experiences gamers, as well as the hardcore gamers.
Here's how I think it should be done... two difficulty levels open from the start. An easy one and a hard one, obviously.
In the hard mode, the flow of the game would be the same. You do the dungeons in the same order, you enter the dungeons the same way, the story is the same, items, bosses, etc.
But the enemies are stronger. All enemies have been made more challenging, especially bosses. But in addition, the dungeons all have remixed interiors, much like Master's Quest. All the dungeons are different, with harder puzzles, harder enemy groups, etc.
I would really enjoy this in a Zelda game, and I think this is something Nintendo should really do.
Although the idea of just having a harder Second Quest wouldn't be a bad idea either.