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!
The Library of Congess's Chronicling America database of historical U.S. newspapers finds nine 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), and one each from the [Liberty, Mississippi] Piney Woods Planter (April 6, 1839), the [Brattleboro] Vermont Phoenix (August 30, 1839, reprinting the 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" (again originating 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.