Stop the Bran hatin'! I love his chapters, they're always full of mysterious tidbits of important information: the three eyed crow dreams, his warging, the Harrenhall tourney, the story about that queen who flew to the night's watch on dragons. When analyzed more closely, GRRM is actually giving us hints from each of these stories which contribute to the overall plot! Bran was the only one that the crow showed a macro view of the imminent threats coming to Westeros. He's going to be important!
Anyways, back on topic, I would also agree that Benjen Stark is not Coldhands. I think he's dead and buried to be honest. Or dead and walking... in any other book I would say he's alive plotting revenge or some such. But this is GRRM, it'd be too convenient for him to pop in at a critical moment, and everyone say " OH he IS alive after all!" People don't like to think he's dead because he didn't go out with a bang like Robb or Tywin did. Or should i say a "twang". Har! He's just...missing.
I do think Coldhands is a child of the forest though, they really don't say how tall he is. He is riding an elk as well (children have been known to ride elks), he summons thousands of crows in a mysterious feat of magic to save Sam from an Other, and he's affected by the magical effects of the wall (he can't pass under it). Also, I don't think Benjen knows how to ride an elk...