The use of red in this context originated from the color of the U.S. penny. The original U.S. copper one-cent (originally called a copper) was issued from 1793 until 1857 and around 1839 people began commonly referring to the coin as a ‘red cent’.
‘Not worth a copper’ is an American phrase that came into use around 1788 and was followed by ‘not worth a cent’ about 1820 according to Stuart Berg Flexner author of "Listening to America". It seems that along with the common use of ‘red cent’ the phrase took on the addition of the word red.
Some sources say that the use of red was a reference to the image of the American Indian that was pictured on its face and red was a shortening of the slang term ‘redskin’ . While I can understand the connection this is not the source since the use of the phrase pre-dated the first issue of the Indian Head penny in 1859.
Image from BCPL.net a service of The Baltimore Public Library