I would say a whole new story would be best. I feel the reason why so many video-game based movies flop is because the creators try and make it just like the game. But there lies the problem: video games aren't done in a three-act structure like a movie. When you try to emulate an experience from a game and put it straight to film without tinkering with the plot, of course it'll turn out crappy. Why I think a Zelda movie could actually work is because the series has a unique advantage. Every game has a different plot with only a few things in common with it's predecessors (Link, Zelda, the triforce, the master sword etc.) so it would be very doable for the filmmakers to actually write their own story with it's own circumstances, it's own characters (aside from the three main characters, of course) and the triforce and all that as the background, just as it is in the games. The only problem is that would take effort, which is something few filmmakers who made video game based movies want to do.
Oh yeah, and absolutely, positively, POSITUTLY don't make it live-action. I said this a million times and I'll say it again: Zelda would fare far better as a light-hearted pixar-esque animated film. Why do I think this? Well, there's just something about the clothes from Zelda that just looks like a costume on real people. Make a live-action Zelda movie and I bet all the actors will look like a bunch of cos-players got a video camera.