Origin of the term "red cent"

Origin

Early 19th century: so named because it was formerly made of copper.

http://www.oxforddictionaries.com/definition/english/red-cent?q=red+cent

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.

Interestingly, Dutch has a similiar expression: "geen rooie cent" ("not a red cent"), which is used to mean "no money at all". This also dates back to the 19th century and refers to red copper cents.

As a historical note supplemental to the fine answers provided by Laurel, Sven, et al., a published 1835 use of the term appears in Clinton Bradshaw; or, The Adventures of a Lawyer, Volume 1, by Frederick W. Thomas. The context contains offensive language, as well as being unfortunately anachronically topical (at least in the US):

As soon as young Pete heard the tramp of the horses, and the voices of the horsemen, he got up on the post, to see who was coming. "By goley," said he, jumping down from the post, and throwing the gate wide open, "there comes Massa Clinton, and that gentlemans what looks like a preacher, that Massa Clinton calls Judge; and another gentlemans. Pete, keep your eye open, nigger -- you'll get something whiter than a red cent." Holding the gate officiously open, he waited the approach of Massa Clinton and his friends.

For the sake of clarity, I remark that Pete, in this excerpt, refers to himself in the third person while talking to himself.

The use of "red" in the quote contrasts the color of copper pennies with the "whiter" hues of the more valuable silver and (remotely, from Pete's perspective) gold coins.

My parents have several sheets of thick stock with red... Coins... stamped into them(about 1/4 Dia) that were issued during WW2 as direct trade for copper pennies. They were called red cents. Noone liked them and most were exchanged for steel pennies when they came out.

There was a catch... They could only be used for food rations. There were also blue ones that had a larger value

https://en.wikipedia.org/wiki/Heller_(money)

Article indicates that the German idiom referring to a coin of very little value, due to the inclusion of copper in the mixture of metal when minting silver coins, caused the coin to gain a red or copper color, and was seen as of very little worth (c. 12th century).
There remains a German phrase/idiom: "keinen (roten) Heller wert", lit.: not worth a (red) Heller, or "not worth a red cent".