I don’t know if you’d count them as major or not, but beyond the Roadrunner theme on Steve and Ed’s demo album “Buck Naked”, I don’t think Barenaked Ladies have ever released a cover. They played plenty in live medleys, but that’s not really the same thing.
Heart’s rendition of “Tell It Like It Is” reached #8 on Billboard.
It could be argued that that wasn’t really King Crimson, as it was an impromptu solo performance by Adrian Belew. They’ve also released their version of David Bowie’s “Heroes.” Crimson’s early live set regularly included Donovan’s “(Get Thy) Bearings” and a “cover” of “Mars” from Holst’s The Planets suite. Both appeared years later on various archival releases, and “Mars” was reworked into “The Devil’s Triangle” on In the Wake of Poseidon, with Robert Fripp claiming the composer’s credit.
As long as we’re beating up Led Zeppelin for their uncredited blues covers, didn’t the original pressing of the fourth album fail to attribute “When the Levee Breaks” to Memphis Minnie?
I was about to say that you could say the same for Gentle Giant–then I remembered their blink-and-you-miss-it version of “Sweet Georgia Brown.”
You’ve got to be joking?
Their first two LP’s are almost entirely filled with covers.
I’m also pretty sure Supergrass don’t have any covers on their albums.
A quick Google found this site , crediting the song to a band called The Clique, and the song by G. Zekley, lyrics by M. Bottler. No, I’ve never heard of them either, but their album with Superman on it is from 1969 according to Amazon.
They covered Chuck Berry’s “School Days” on their first Australian album, T.N.T.
You’re right about the ballad thing, though…unless you count “Night Prowler”? 
Also, side four of Alive II, which may very well be the worst live album ever made, consisted entirely of studio cuts, and included a cover of “Then He Kissed Me”- appropriately retitled to “Then She Kissed Me”.
I don’t think Black Sabbath did any covers.
Oh, and the Stones have also covered “Twenty Flight Rock” and the Temptations “Imagination”.
And I think that cuts from live albums should count in this category. If it made it to disc, and was released to the marketplace, it counts.
Gee, they must scratch easily then.
It was actually a medley of “Pick A Bale Of Cotton, On Top Of Old Smokey, Midnight Special.” And it was never intended to be recorded or released. Apparently ABBA would just goofing around in the studio to check the equipment, and this selection got on the tape.
They did Aynsley Dunbar’s “Warning” on their first album.
New Order covered Keith Hudson’s “Turn The Heater On” for a Radio 1 session that later was released on record. Not sure whether that’s counted as live or not.
This question is probably going to require a band that shined brightly very briefly, then vanished for one reason or another.
To mention one such band, Nirvana nearly fits the OP’s bill. They recorded only one cover on their three studio albums, the Shocking Blue’s “Love Buzz” on Bleach. There were a few covers on their Unplugged album (Bowie’s “The Man Who Sold the World”, most notably), but none on The Muddy Banks of the Wishkah.
I don’t think Iron Maiden has ever done any covers. Now someone will probably come along and tell me one of their songs I thought was an IM original is actually a cover.
They covered “Bo Diddley” by Bo Diddley (who was their musical inspiration).
I have a very-scratched-up copy of the single by The Clique.
The R.E.M. version kicks its ass, by the way.
A quick perusal of their allmusic.com Discography entry reveals no covers on their studio albums. I didn’t see any on their live ones, either. There is a section on Maiden’s Main Details page, however, that lists “Performed Songs By”, and this includes Thin Lizzy’s Phil Lynott, the early-70s proto-metal band Mountain, and Tull’s Ian Anderson. But I’m having a hard time tracking these down.
The Cars?