I think that this concept could work depending on exactly how customisable Link is. Like MsNerrrrd up there, I am a bit of a traditional gamer. When something has been consistently established within a game, I am not quick to accept a change. For example, I always picture the assassins as wearing hooded white robes in Assassin's Creed, I always see mario as wearing a red shirt, blue overalls, and that signature red cap, and I always think of Link as being a young man garbed in a green tunic. Being able to change Link's appearance with a wide range of attire and a new haircut would be a great addition to the series, but I don't think he should physically change much. I would want him to keep his standard look (the Hylian trait of pointed ears, his facial features, ect.). This desire to keep Link the same as he is now wouldn't be all that hard to satisfy, though. Link's normal look, I assume, would be what the default appearance would be anyway. Adding facepaint, tattoos, and various other items to (possibly) affect gameplay would also be a good way to implement this idea (I'm a fan MGS3 and how they handled this concept).
As a side note, I also would not mind the addition of a gender option for Link (each Link is different, after all).