TL;DR: Benjen Stark is probably not Coldhands.
“They killed him long ago.”
-Leaf, A Dance With Dragons, Bran II
Benjen Stark, brother of Lord Eddard Stark and uncle to Bran Stark, Robb Stark, Jon Snow and the whole Stark clan, went missing early on in the A Song of Ice and Fire series and has not been heard from again.
Benjen was a man of the Night’s Watch, and he was their First Ranger. He went out on a ranging with six rangers to find Ser Waymar Royce, who had not returned after a ranging of his own.
After Benjen does not come back for a period of time, the Night’s Watch sends additional searches for him. He had marked trees during his ranging — which the ranging to find him could see — but those markings stopped in the stony highlands. That was the last we’ve heard from Benjen.
[T]hey’d found nothing aside from a few blazes in the trees that his uncle had left to mark his way. In the stony highlands to the northwest, the marks stopped abruptly and all trace of Ben Stark vanished.
-A Game of Thrones, Jon IV
Some of the rangers Benjen was with were later found (dead), but Benjen was not.
So why think he could be Coldhands?
For starters, Coldhands seems to take a liking to Bran, and if Coldhands is indeed Benjen, that connection would make sense, given their relation.
Additionally, Coldhands is dressed like a man of the Night’s Watch and is very adept at surviving in the cold climate of the North, like a ranger would have to be.
“There’s not a man on the Wall knows the haunted forest better than Benjen Stark. He’ll find his way back.”
-A Game of Thrones, Bran IV
There are some other “hints” as well, although they are weak supporting evidence at best. Benjen Stark has been missing north of the Wall since almost the very start of the series, and Coldhands is found north of the Wall. At the very least, that puts them in the same general location, although just because they are both “North” doesn’t mean much.
What’s the evidence against Benjen Stark as Coldhands?
Unfortunately, this theory seems to have been completely debunked. George R.R. Martin has outright stated that Benjen is not Coldhands — a fact that was dug up in the original A Dance With Dragons manuscript by reddit user _honeybird.
The quote shared at the beginning of this post also serves as evidence against the “Benjen is Coldhands” theory. Benjen has not been missing for that long, but the Children of the Forest say Coldhands has been dead for a long time.