The earliest instance I can find for "red cent" is as part of the idiomatic expression "not worth a red cent," meaning "worthless." From "The Pressure," in the [Bloomsburg, Pennsylvania] Columbia Democrat [May 13, 1837):
There is a great fuss made by the City papers about pressure and failures, and really if a person knew nothing of the world, he would imagine that all the riches and honors of great men were scattered to the four winds of Heaven—because it would be ludicrous to suppose that they should fall to the lot of poor and humble citizens. But how ridiculous is all this palaver and excitement, when we know the cause in most instances. For example, many of these "unfortunate" business-men were not worth a red cent three years since; but they commenced speculating in stocks, and buying lands in the West and Texas, upon a credit that had nothing to lose and all to gain; and when payment is demanded, and the banks refuse to discount their paper, why they fail!
And from John Crockett, "Selected Tale," in the Richmond [Indiana] Palladium (July 7, 1838):
I have no doubt I could obtain thousands of Mr. Thomas H. Benton's speeches, without cost to me, but thy would be paid for out of the people's money; and to be candid and frank upon the subject, sir, I must say that if I could obtain a million of them for a red cent, I have too much respect tor my franking privilege to be guilty of so gross an abuse of it as I believe I would be to frank even one of them.
The Library of Congress's Chronicling America database of historical U.S. newspapers and the Elephind combined database of various state newspaper archives find thirteen mentions of "red cent" from 1839—two from the Liberty [Mississippi] Advocate (May 30, 1839, and August 29, 1839, the latter reprinted from the New Orleans [Louisiana] Picayune), two from the Maumee City [Ohio] Express (June 1, 1839, reprinting the same New Orleans Picayune story, and October 19, 1839, reprinting an item from the Cincinnati [Ohio] Buckeye), two from the the [Brookville] Indiana American (May 24, 1839, reprinting a different New Orleans Picayune item, and July 12, 1839, reprinting an item from the Indiana Democrat), and one each from the Pontiac [Michigan] Courier (March 8, 1839), the [Liberty, Mississippi] Piney Woods Planter (April 6, 1839), the [Brattleboro] Vermont Phoenix (August 30, 183, reprinting the first New Orleans Picayune item), the [New York] Morning Herald (July 30, 1839), the Charlotte [North Carolina] Journal (June 27, 1839, reprinting the May 30 Liberty Advocate story), and the [Washington, D.C.] Native American (June 29, 1839, reprinting the same). Yet another instance of "red cent" (the third one to originate in the New Orleans Picayune) appears in "the [Houston, Texas] Telegraph and Texas Register (May 8, 1839):
An evidence of smartness.—What kind of fellow is C——? said a chap the other day to Flam.
Smart, very smart, said the wag.
How so? how do you call him smart?
Why, he has been living two years, to my knowledge, without earning the first red cent, and had no capital to commence with. If that isn't an evidence of smartness, I don't know what is.—Picayune.
Christine Ammer, The Facts on File Dictionary of Clichés, second edition (2006) finds another example from 1839:
red cent, not worth/don't have a Worthless; bankrupt or broke. The cent has long been the lowest denomination of American coin, and "red" refers to the fact that it used to be made out of copper. The expression dates from the early nineteenth century. J. S. Jones used it in People's Lawyer (1839): "It would not have cost you a red cent."
The citation to Joseph Stevens Jones is to a play he wrote (and first published in 1839) titled Solon Shingle, Or, The People's Lawyer: A Comedy in Two Acts. In this instance, as in some of the others from 1839, the red cent appears independent of the "not worth a red cent" expression.
It seems plausible to me that the red in "a red cent" serves the same intensifying role that thin does in "a thin dime": Just as all dimes are thin, all cents (that is, pennies) at the time of the expression's first appearance were red (copper). The only thing to be gained by adding red to "a cent" (or thin to "a dime") is emphasis on the following noun. On the other hand, since 1837 was the year that U.S. pennies went from pure copper to 95% copper (as detailed in a link in Laurel's answer), perhaps "red penny" is a reference to the older, slightly purer (but no more valuable) type of penny.