For visiting dungeons in a different order, you could add a Kingdom Hearts style system. You have a bunch available (E.g water, fire and forest), but after one is complete, the difficulty ups in the other two, then once the second is complete, the remaining dungeon gets even harder. Once all 3 are complete, the story advances. Or make it more intricate, so say you get to the middle of the Forest Temple, but can only get a boomerang then you are stuck. You would eventually go to a different dungeon when you get bored, and in that dungeon you find an area in which you need the boomerang. Once the puzzle is complete, you get a hookshot which can be used to progress in the Forest Temple, thereby linking the temples together.
Another brainwave- For multiplayer, have a seperate standalone mode, much like Farcry 3, which tells the backstory to the game in question- if it was two-player co-op, you could play as two Sheikah for example, who try to to the events of the
game happening as they are aware of the evil, but though they ultimately fail, there could be a twist where one falls into a deep sleep and becomes a sage and once that is complete, a new dungeon opens up in the single player game to rescue the sage- once you have done so, you have the option to play as him instead of Link!
I should probably insert some witty or meaningful piece of text here.