The concept of "Zelda" is exactly the thing they own, want to protect their ownership of so they can continue being the sole seller of Zelda-related things in the future, and are quite unlikely to grant anyone permission to use. Doesn't hurt to ask them if you want to, but just be aware they get asked this hundreds of times a year and they have a history of saying no, as does pretty much every major game company when asked if people can use their IP.

Does it really have to be based on Zelda?? Just do everything exactly the same and change the names and character art.

Would I email Nintendo and ask if i can use it or is there some long process i need to go through?

Well I don't now which department you would email but understand its not just a case of one studio going to another and saying I want to use part of the lore from this game you've made. Nintendo arent getting anything out of letting you use the zelda name, they'll want cash or something, and we aren't talking 25 dollars or something. We're talking big bucks, funds only available to corporations.

It might just be easier to go with making your own character names up, you have a story, just remove any direct references to zelda and make up some random names to replace them. The gameplay itself doesn't have to change.

Probably much easier than getting nintendo's permission. Chances are that there are hundreds of people with the same idea as you (ie using the zelda or mario name or something like that) that they just ignore any emails like that and mark them as spam. Now, if its a game being distributed to friends then chances are nintendo will just turn a blind eye, but if you've put the work into making something and its enjoyable you would like to at least make it available publically. Ditch the zelda theme,