George does not write shit in his books for no reason, and he goes to great length to introduce the story of "the Nights king" and his Cold bride before we run into Coldhands for a second time. I think its page 629 & 630 of the large version of Storm of Swords.
He kinda clearly said that "The Nights king" gave his seed to this un-dead bride and with it his soul. I am taking this for the birth of the Coldhands Character. I mean it directly relates to the Nightfort, cold hands knows the way in and shows Sam but cannot go there himself... I dunno read it yourselves again, but I really this that story was put in to give you some ideas of where cold hands might have come from. but yeah, I really think ColdHands to be a relation of the Nights king and Wight Bride.
A Storm of Swords, Chapter 56, Bran said: