If I understand the late Bruce Olson correctly, he seems to say the song originated in a parody later given shape by the celebrated singer-songwriter Dibdin. Judging by the scansion, it may not have used the tune we're familiar with (the later verses can be fitted to the tune only with difficulty). I quote from Olson's collection at erols.com:

"About 1600 a ballad came out on 'The Noble Acts, newly found, of Arthur of the Table Round,' commencing, 'When Arthur first in court began, and was approved King.' This was parodied in the 17th century. A 17th & 18th century version goes:

When Arthur first in court began
To wear long hanging sleeves,
He entertained three serving men,
And all of them were thieves.

The first he was an Irishman,
The second he was a Scot,
The third he was a Welshman,
And all were knaves, God wot.

The Irishman loved usquebaugh,   [whiskey]
The Scot love ale called blue-cap,
The Welshman loved toasted cheese,
And made his mouth like a mouse-trap.

Usquebaugh burnt the Irishman's throat,
The Scot was drowned in ale,
The Welshman had like to be choked by a mouse,
But he pulled it out by the tail.

But a version printed in 1781 commences 'In days when good King Stephen reigned.' Somewhat later we find in 'THe Universal Songster, III, p. 430, 1828 (attributed to T. Dibdin):

A Parody Glee Air: When Arthur First in Court Began

Wheb Richard Lion ruled, why, thyen
The Saxons wore long robes,
He entertained three serving-men,
And all of them were rogues.
The first he was a miller bold,
The next he was a weaver,
The third he was a tailor, good lack,
And they were rogues together.

The miller he stole grist from the mill,
The weaver he stole yarn,
The tailor he stole broadcloth
To keep the other rogues warm.
But the miller he got drowned in his mill-dam,
The weaver got hung up in his yarn,
And Tailor Dick went plump to Old Nick]
With the broadcloth under his arm."