1) I think Coldhands is Benjen Stark who was killed while ranging.
2) I think he was never a wight but was resurrected by the Three-Eyed Crow as an ally or assistant in much the same way as Beric Donderrion and Lady Stoneheart were brought back - this explains his autonomy compared to wights.
3) I think the fact that Benjen was dead for awhile in the cold North before being brought back accounts for his black hands (i.e. frostbite would quickly set into the extremities).
4) I think the Three-Eyed Crow is Bryndon Rivers aka Bloodraven who may or may not be "bodiless" now and has survived so long due to being able to warg from creature to creature or maybe even with many creatures at once (may even be warged with Mormont's raven?)
5) I believe the spoiler chapter notes that we've seen concerning Varamyr Six-Skins may lend some support for #4 above.
6) I think the name "Three-Eyed Crow" is a big clue that he is Bloodraven. First, Bloodraven with his one eye warged with a crow or raven would literally make a three-eyed crow. Or, second, a NW brother or "crow" who had the ability to warg and/or perform sorcery could be thought of as "opening their third eye" and, thus, would be a "three-eyed crow".
7) I don't think Coldhands controlled the elk and ravens when he rescued Bran and the other kids from the wights. I think it was the Three-Eyed Crow helping them.
8) I don't believe there are different kinds of magic (i.e. fire, blood, shadow, warging, etc.) I believe there is only "magic" that is manifested, or used, in countless different ways. A possible exception to this is the magic of the Old Gods (i.e. warging, green dreams, etc.) It could be that Bloodraven is/was a very unique individual in that he was Valyrian on his father's side and Blood of the First Men on his mother's side so he could both perform sorcery and Old God magic? Hmm...maybe? :dunno: Also, if this is the case, what could it mean for Jon who "might" have a similar heritage?
9) I think Coldhands couldn't pass through the Black Gate because the Wall, or at least the Black Gate, is warded against sorcery in general and not just so-called "Other" magic.