The internet is a wondrous thing, it lets you dig deep down through all the stuff floating around. So apparently this attribution of gemstones to apostles goes back to the Book of Revelation 21 and the first to make a connection between the gemstones mentioned there and the apostles also mentioned there, although the latter not in a particular order, was Andrew or
Andreas of Caeserea. Now there's a PhD thesis, written in 2008 by Eugénia Constantinou, and you can download it
here . It has the actual text of what Andreas wrote in his commentary on the Book of Revelation in the year 600 or thereabouts and it says this:
Rev. 21:20a the fifth [stone is] onyx
[245] By this (stone) having the appearance of a shining human fingernail, is probably meant James, the first who accepted bodily death for Christ before the others, which the onyx characterizes (like a nail), being deprived of sensation when it is cut off.
So this very first author attributes the onyx to Saint James the Greater and not chalcedony and he has quite a different explanation.
Apparently later, others used various different lists of apostles' names and then attributed the gemstones listed in the Book of Revelation according to the chosen sequence of apostles' names. I did not pursue this any further because I have the impression that this did not play a major role in (Western) Christian theology and Christian art of the Middle Ages. The connection between precious stones and apostles seems to be popular with collectors of gemstones and people who are into zodiac interpretations and the like.
I can't find anything whatsoever on who and when someone attributed red hair to the Apostle James. As
@Paladina said already, red hair got attributed to Judas Iscariot; this was apparently particularly popular in Spanish art and spread from there to other parts of Europe.