The Telegraph has a story about research into the Neandertal genome that suggest that at least some of them had red hair and even freckles. The article states:
After analysing the fossil bones found in a cave in north-west Spain, the experts concluded they had human blood group "O" and were genetically more likely to be fair skinned, perhaps even with freckles, have red or ginger hair and could talk.
The investigating team from Spain's government scientific institute, CSIC, used the very latest forensic techniques to remove the bones for analysis to prevent them getting contaminated with modern DNA.
Presumably they found FOXP2 (oddly truncated from "Forkhead Box P2"), one of the genes responsible for the capacity for speech. The article doesn't say. So, it looks like the northern European dermotype traits go back a ways.