If I could suggest using a previous companion before in way so that isn't really the same companion, what about using the next Princess Zelda as a spirit companion? As long as it isn't the same Zelda from Spirit Tracks then it isn't cheating. Of course she'll need a different reason for being out of her body, like say a coma.
Or, this is a real big one. Link's partner could be some floating flicker of fire with a voice who guides him through his journey until the very end, becoming a sort of close friend and ally until it's revealed he tricked Link. Why? Because the little fire is actually Ganondorf's spirit, using Link to deal with a traitor in his army and make Link bring him back to life.
I always thought it would be interesting to have Link carry around a poe flame in a lantern as a companion. A companion whose goal perhaps is to be released by Link - or at the very least is not particularly concerned with petty mortal details such as Link's continued existence. It knows a great deal about monsters and whatnot, but sometimes it decides to be cryptic or misleading in order to trick and confuse Link. I think it would be interesting to play with an unreliable guide for once, as opposed to a guide who apparently has nothing better to do than help you out at all times, unconditionally.
If anyone has played American McGee's Alice, I would like a guide similar to the Cheshire Cat. Sometimes, the cat would give good advice. Other times, it would troll you or say something completely irrelevant.
But that's unlikely considering that poes are evil, and the point of a guide is to make the game easier and not harder. I would still like to see this, though - for what it's worth.
I don't know, I just thought of this but I think it would be really cool for link to have a Sheikah as a companion.
Maybe a young Sheikah in training, that must go on a quest with Link to train. They wouldn't always be together but they could communicate somehow when far away from eachother and they could co-operate in the dungeons.