Smashing Pumpkins
Hm... Machina II was released for free, on mp3, by the Smashing Pumpkins right when they were breaking up. So yeah, Radiohead isn't the first one. However, Radiohead is pretty well known; that and the fact that Smashing Pumpkins actually gave away the "album" for nothing, it was more like a final "f**k you" against the record labels.
So Radiohead would be the first "big player" that actually moves into this arena. Some indie groups have already done it, though I don't really think they have done it the "right way"; local group "Veo Muertos" (literal translation: I SEE DEAD PEOPLE) decided to sell online its album ... on iTunes. Which sucks as His Jobsness has not opened iTunes for Mexico.
Anyway, it seems it would be these indie groups the ones that may have motivated Radiohead and Madonna to ditch their records, and with this, maybe more will follow...