There is speculation on who Coldhands is, as described here and here, for example. I'll discuss the The Last Hero and Benjen Stark theories. And also a theory of my own.
The Last Hero is the person from Old Nan's story about the Last Hero who went out into the cold north with a squad of men, and was hounded by the Others, seeing his friends, his horse and even his dog die. I believe she tells him this story right after he wakes up from his coma. Quote from the wiki:
Thousands of years ago, a winter fell like no other, and there came a
night that lasted a generation. The Others came during that winter,
and they hated fire, iron, and the touch of the sun. This was before
the Andals had come, and before the women of Rhoynar, when the First
Men lived in the lands they had taken from the Children of the Forest.
The Others had slaughtered many, and couldn’t be stopped, so the last
hero of the First Men set out to find the Children. He left with his
sword, a dog, his horse and twelve companions. When only he was left,
in despair of ever finding the Children, the Others closed in.
The connection between this hero and the Children, who we now know to be connected to Coldhands, somewhat supports the theory of them being one and the same.
The theory is also somewhat supported by Leaf saying "He died long ago", which may imply that "long ago" is too long of a time span to be anyone who died recently, seeing how she is reportedly very old herself.
One interesting piece of information about "The Last Hero"-Coldhands is that he knows about the Old Gate at the Nightfort, which only brothers of the Night's Watch may pass. Presumably, its existence is not common knowledge, and may imply that Coldhands lived long ago. Although it is easily thwarted by things like (Spoilers for ADWD):
It may be Bloodraven's/The three eyed-crow's knowledge, which is fairly believable, as we know that he is very well versed in magic, and knows the Wall well, having been the Lord Commander. And: Someone like Benjen Stark might very well have access to such rare knowledge.
However, while cold preserves, it does feel -- to me, at least -- a bit unbelievable that even an undead, stored in freezing cold, could last thousands of years.
The evidence of him being Benjen Stark, are even more meager. I believe all we have going for that theory is:
- He is reportedly a former man of the Night's Watch, as evidenced by him calling Sam "Brother" and wearing black clothes.
- He saves Sam, is an ally of the Children and the three-eyed crow, and seems to be on the side of the good guys.
- His appearance in the story coincides with Benjen's disappearance.
All of which are pretty weak, as evidence goes. For example, he could easily be lying about being a black brother, or it could be some misunderstanding that he just never denied. Him being a "good guy" could simply be a direct effect of him being the three-eyed crow's minion. And of course, many people disappeared around the time Coldhands appeared, and plenty of black brothers died on the Fist, right before Coldhands appearance.
The single strongest motivating factor (not evidence!) for Benjen = Coldhands might be that people want it to be him: Rather than him being dead, having him reappear as a good guy, taking care of Bran. I myself am one such person, although I would prefer if he would reappear alive.
Hence, my theory largely stems from the happy moment when Sam was saved by Coldhands' flock of ravens, and I was thinking: "So this is what happened to Benjen!"
One idea that I do like is the combination of the two: That Benjen's fate is shadowing the fate of The Last Hero from Old Nan's tale; that his is a role that is repeated, much like Azor Ahai's.
A personal theory of mine (spoilers ADWD):
is that Coldhands could be a friend of Bloodraven, from his days in the Night's Watch. Since he was Lord Commander and a magic user, it could easily be one of his former brothers. Which would make sense of the connection between them, rather than Coldhands being just any random person. It would also support Leaf's statement "He died long ago." since Bloodraven is fairly old.
For a wild moment, I was considering if he could be Dunk, but that would be unlikely, as Dunk is known to have perished at Summerhall with Egg. We do know that Bloodraven aka Brynden Rivers came to the wall with the honour guard who escort Maester Aemon to the wall, so if this theory is correct, we could find Coldhands among those. There should have been some fairly important names in that group.
While this theory would be interesting, I am much more in favour of the Benjen theory. It feels right, and it feels better.
In short, there is no clear evidence as to who Coldhands is -- or was, before he died. I would say that many things point to his identity being irrelevant, since wights do seem to lose much of their personality when they die, and it is plausible that all we see of Coldhands personality is actually the three-eyed crow's.
My gut feeling is that Coldhands' (former) identity will be revealed. Mostly because GRRM built up some suspense around his character and purposely did not let Bran see his face. And also because I think we will know the fate of Benjen eventually, and as I said, I am a believer in the particular theory that binds those two mysteries together.
