The earliest Google Books match for the phrase that I could find is from Emma Southworth, The Hidden Hand, Or, Capitola the Madcap (1859):
"Hum! you are like the Bowery boys in times of peace, 'spoiling for a fight.'"
"Yes, I am! just decomposing above ground for want of having my blood stirred, and I wish I was back in the Bowery! Something was always happening there! One day a fire, next day a fight, another day a fire and a fight together!"
Besides, there seemed just now nothing to do—no tyrants to take down, no robbers to capture, no distressed damsels to deliver and Cap. was again in danger of "spoiling for a fight." And then Herbert Greyson was at the Hall—Herbert Greyson whom she vowed always did make a Miss Nancy of her!
In this example, the second speaker in the initial conversation explicitly equates "spoiling for a fight" with "decomposing" above the ground"—that is, going to waste or wasting away in the vegetative sense. The missing but implied element in the phrase is "for want of," as in "spoiling for want of a fight." I see no reason to doubt that this was the earliest sense of the expression.
The author, E.D.E.N. Southworth, grew up in Washington, D.C., but also lived in Wisconsin before 1859. The Hidden Hand was first published in the New York Ledger, according to Wikipedia.
The earliest instance of "spoiling for a fight" in the Library of Congress's Chronicling America newspaper database is from the [Baltimore, Maryland] Daily Exchange (June 1, 1858):
In the Senate of the United States on Saturday, there was "great cry and little wool." Talk and nothing but talk has, thus far, been the only result of all the indignation excited in this country by the insolent proceedings of the British cruisers on the Gulf of Mexico. Senator MASON offers a string of resolutions, in affirmance of general principles, which nobody doubts, and which have been affirmed and re-affirmed any time these fifty years by succeeding generations of American statesmen. Senator TOOMBS who announced his readiness to whip Great Britain, more than a week ago, and who has been spoiling for a fight ever since, continues implacable, and refuses to be appeased until "the aggressors upon our rights" have either been "sunk," or otherwise brought to "condign punishment."
The same database yields seven unique instances of the phrase from the following year, in the Delaware [Ohio] Gazette (February 4, 1859), the Burlington [Vermont] Free Press (April 29, 1859), the Cincinnati [Ohio] Daily Press (May 7, 1859), the [Honolulu, Hawaii] Pacific Commercial Advertiser (September 1, 1859), the Cadiz [Ohio] Democratic Sentinel (September 14, 1859), the [Charlotte, North Carolina] Western Democrat (October 11, 1859), and the Richmond [Virginia] Dispatch (October 13, 1859). It thus appears that the expression caught on and spread rapidly in the United States in 1858–1859.