There's quite a useful page dedicated to the rhyme, with a number of versions included at this site. They claim a version in Richard Grafton's "Chronicles of England and date it 1590. Grafton died circa 1572 and based his Chronicles on a rhyming chronicle to 1438 by John Hardyng (1378-1465). One or both of these appear to have been a source for Holinshed, so the Opies' conclusions make sense so far.

The following version occurs in John Day's "The Return from Parnassus", 1601.

Thirty days hath September,
April, June, and November,
February has twenty-eight alone,
All the rest have thirty-one;
Excepting leap year,--that's the time
When February's days are twenty-nine.
   
According to this site the verses were originally written by Grafton in 1568. They give the following version

Thirty days hath September
April, June, and November;
All the rest have thirty-one,
Excepting February alone,
And that has twenty-eight days clear
And twenty-nine in each leap year.

In the same year that the Opies published their Dictionary, though, appeared a volume called "Secular Lyrics of the XIVth and XVth Centuries" (R. H. Robbins, ed., Oxford: Clarendon Press, 1952). In it is the following from British Library Harley MS 2341, fol. 5r.

Thirti Dayes hath Nouembir
Thirti dayes hath Nouembir,
April, June, and Septembir;
Of xxviijti is but oon,
And all the remenaunt xxxti and j.

This is loosely dated between 1300 and 1450, though I don't know the basis of this. The Opies (perhaps unsurprisingly) have not amended their Dictionary in later versions. This rhyme is available in Representative Poetry Online here.

:-)
Ian