In the previous discussion of the song (see IanC's post above), Bruce Olson mentioned an early example on his website. This is When Arthur first in court began; it is a parody of "The Noble Acts, newly found, Of Arthur of the Table Round," (Thomas Deloney, c. 1600). Falstaff sings the opening lines in Henry IV, II, iv (1598). Bruce also refers to a version printed in 1781, beginning "In days when good King Stephen reigned", and quotes another, slightly later, "When Richard Lion ruled, why, then". Another parody, "When James in Scotland first began", appeared in 1656. The early versions were sung to a form of the popular Flying Fame / Chevy Chase melody.

A broadside example of the Deloney piece can be seen at   Bodleian Library Broadside Ballads:

The noble acts newly found, of Arthur of the table round   Printed between 1674 and 1679 for F. Coles, T. Vere, J. Wright, and J. Clarke [London]. Wood 401(61)