Executive Meddling: The game was originally supposed to be an expansion to OoT, titled "Ura Zelda". However, when the designers expressed displeasure with this idea, they were challenged to make a new adventure in 1 year.
Fan Nickname: The Legend of Zelda: Link in Wonderland for the game.
The game began development for the N64 add-on called the 64DD (or the "Nintendo 64 Disk Drive"), and was going to make use of some of the add-on's features. The game would have used a real time clock instead of the in game one, and was going to use a full 7 day week instead of three days like the final game, but these were dropped from the final product since there were difficulties trying to get these features to work on standard N64 hardware (even with the required RAM expansion pak). There was also a proposed feature regarding being able to "buy extra time" from a merchant who... sold time, but the change to the clock system and lessening of days made the merchant seem less important.
Instead of the Fierce Deity's Mask, there was going to be a mask in the game that would have let Link turn into his adult self from Ocarina of Time (evidence of it's existence can be seen in really early screenshots). This mask was scrapped for being mostly useless since all major equipment could be used by young Link this time around. Not wanting to let the "adult Link" aspect go to waste, however, the developers put in the Fierce Deity's Mask instead as a 100% completion bonus that's required to use on the final boss in order to see the Golden Ending.
Early screenshots also display various changes to textures throughout the game. A small example is that the Deku Pipes originally were colored white instead of brown, but a much bigger example is some of the wall textures for both inside and outside of Clock Town. The textures originally were a bit more surreal with weird-looking suns, but in the final game the walls textures instead got somewhat less surreal looking designs. Perhaps another very interesting change is that Link was originally going to have the Kokiri Shield from Ocarina of Time return in place of the Heroes Shield (or perhaps as an alternate starting shield), and the Kokiri Sword originally looked exactly like how it did in Ocarina.
One image taken from the earliest stages of development showed that all three Gorman Brothers were originally just one Ingo, and might've worked for Cremia at one point instead of having competition against her.