Christine Ammer, It's Raining Cats and Dogs... and Other Beastly Expressions (1989) dedicates a rather modest two paragraphs to a discussion of the possible origins of the expression:
The British origin of this expression for a heavy downpour makes perfectly good sense, given that the country's notorious reputation fro rainfall. Two centuries before Shaw composed his concluding refrain to an Irish song ["At last I went to Ireland,/ 'Twas raining cats and dogs:/ I found no music in the glens/ Nor purple in the bogs." 1931], Jonathan Swift had written "I know Sir John will go, though he was sure it would rain cats and dogs" (1738), using a term that was already a cliche.
The expression's origin is cloudy. One writer says it comes North European myth, where cats supposedly have great influence on weather and the dog is a symbol of wind; hence the cat denotes heavy rain and the dog strong wind gusts. Another suggests the analogy of a raging storm to the hubbub of a cat-and-dog fight. Perhaps a more literal meaning is the true source. In 17th-century Britain, after a cloudburst, the gutters would overflow with a filthy torrent that included dead animals, along with sewage and other debris. Whatever the source the phrase called up an image picturesque enough to persist and be passed down to the present.
Inspired by Phil M Jones's find of an instance of "rains Dogs and Cats" from 1678, I searched for "Dogs and Cats" (and "Cats and Dogs") in a database of pre-1700 English books—and found two even earlier instances of the expression in the same "dogs and cats" order. From Thomas Flatman & John Phillips, Don Juan Lamberto: or, a comical history of the late times, part 2, chapter 4 (1661):
Now you must understand that after the Knight of the Golden Tulip was retaken through the great Courage of the Knight of the Bath, he was secured in the Castle of the Lyons, and eke the Knight of the Mysterious Allegories was there secured also, so that they had often opportunities to discourse together. Now when they saw each they congratulated one another right lovingly; Quoth Sr. Vane I am right glad to see you Sr. Lambert, though not so glad to see you here, however it is better to be here than in the open Fields, where there is no shelter against the Rain, nor any other kind of storm that should happen, for here we have Houses over our heads, so that if it should rain Dogs and Cats we could have no harm. And by the Masse quoth Sr. Lambert you speak right cunningly Sr. Vane; And besides this we do not fear to have our Corns trod upon by the Horses of the enraged Charrioters, nor are we in danger to be bruised by those sturdy Gyants ycleped Carrmen, nor need we fear to have our mantles snatch'd from us going late in the direul plain of Lincolns-Inna; however Liberty is worth its weight in pure Gold.
And from Maurice Atkins, Cataplus, or, Aeneas, his descent to hell a mock poem in imitation of the sixth book of Virgil's Aeneas, in English burlesque, page 19 (1672):
Where e're I went on Land or water
Hee'd make a shift to follow after.
Neither had he flincht a foot, had fates
Made it rain down dogs and cats;
Though old was body and decrepit,
Yet heart was whole and nought could break it.
It is quite striking that John Phillips, the person credited with the 1678 instance that Phil M Jones's answer cites was the coauthor of the work from 17 years earlier, where "rain Dogs and Cats" also appears. It is almost as surprising that the second occurrence of the phrase appears in a mock poem imitating the sixth book of the Aeneid—and that six years later the second Phillips match for "rains Dogs and Cats" is a burlesque imitation of the fifth and sixth books of the Aeneid.
As Mehper C. Palavuzlar's answer observes, there is an even earlier instance of raining dogs and polecats. The source is Richard Brome, The City Wit, act 4, scene 1, at line 1721 (first performed circa 1629–1631), published in Five new playes, (viz.) The madd couple well matcht. Novella. Court begger. City witt. Damoiselle (1653):
Sarpego. Where is your Mistresse? I mean your grand Matrona, Mrs. Sneakup.
Bridget. In the first place let me beseech you Sir,/ Vouchsafe your answer to a longing Maid,/ That can be comforted in nothing more,/ Then the good newes of your prosperity;/ Of which I hope a part at least to be,/ Preferr’d by your late promise to your service.
Sarpego. I will now breath a most strong and Poeticall execration/ Against the Universe.
Bridget. Sir, I beseech you ...
Sarpego. From henceforth Erit Fluvius Deucalionis the world shall flow with dunces; Regnabitque, and it shall raine/ Dogmata Polla Sophon, dogs and polecats, and so forth.
Bridget. His Court advancement makes him mad, I fear.
The joke here is that "Dogmata Polla Sophon" translates from Greek (according to Google Translate) as "Doctrines of Many Wise Men." It is only in the mouth of the character Sarpego that dogmata becomes "dogs," polla becomes "polecats," and sophon becomes "and so forth." Regnabitque, too, is reduced from something associated with the Latin word for kingdom to "rain."
At this point, I am aware of one instance (from circa 1629–1631) of raining dogs and polecats, three instances (from 1661, 1672 and 1678) of raining dogs and cats, and no instances before 1700 of raining cats and dogs. Those results provide some (but not much) circumstantial evidence that "raining dogs and cats" is older than "raining cats and dogs," and that "raining dogs and polecats"—reflecting a false-cognate-based nonsense translation of Greek and Latin phrases into English—may be the oldest of all. At the very least it provides evidence that people were writing about downpours of dogs and polecats by 1631 and of dogs and cats by 1661.
The earliest match for "rain dogs and cats" that I found, from Don Juan Lamberto (1661), involves one character telling another that since they are in a house, and not in the open fields, they are not subject to harm from "Rain, nor any other kind of storm"—including, specifically, a rain of dogs and cats. To my mind, this sounds like a literal falling from the sky of domesticated animals. It makes no sense to me to emphasize the "Houses over our heads" as keeping the two conversants from harm in such a storm if the expression ultimately refers to animals falling through roof thatching or floating dead in overflowing sewers.
It is possible, of course, that the expression "raining dogs and cats" was decades or centuries old when the authors of Don Juan Lamberto put it in their book. If so, the particular circumstances in which it appears there isn't especially helpful in revealing the original understanding of the expression. It is even possible that the jokey translation of "raining dogs and polecats" in The City Wit (1629–1631) is the original ancestor of "raining cats and dogs."
Nevertheless, I think it is quite plausible that the origin of the expression is no more odd and mysterious than someone looking out the door or window at a heavy downpour and saying, "It's raining so hard that I wouldn't be surprised if dogs and cats started coming down in it, too."