As I note in a comment beneath Mari-LouA's thoughtful answer, I have for a long time been struggling to provide a definitive answer to this question. At this point, perhaps I should throw in the towel and simply note the early (but ambiguous) examples I've found, followed by earliest occurrences of the modern versions "rule the roast" and "rule the roost." Here's what I have.
First occurrences of 'rule the rost/roste'
The earliest instances I've been able to find involve the ambiguous spellings ""rule the rost" and "rule the roste." Two are from John Skelton. First, from Skelton, Magnyfycence (1516, according to Encyclopædia Britannica):
Courtly Abusyon. Cockes bones, I ne tell can/Which of you is the better man,/Or which of you can do most.
Crafty Conueyance. In faith, I rule moche of the rost.
Clokyd Colusyon. Rule the roste! Ye, thou woldest/As skante thou had no nede of me.
Crafty Conueyance. Nede! Yes, mary, I say not nay.
Courtly Abusyon. Cockes ha[r]te, I trowe thou wylte make a fray.
Courtly Abusyon's tendency to use "Cockes [this or that]" as an oath invites modern readers to read the rost as being a perch in this case, but I'm not persuaded that it is more than a coincidence that "Cockes bones" and "Cockes ha[r]te" book-end "rule the roste" in this excerpt.
From Skelton, Colin Clout (ca. 1518), cited in an 1871 issue of Notes and Queries:
But at the pleasure of me/That ruleth the roste alone
And again from Skelton, describing Cardinal Wolsey in Why Come Ye Nat to Courts? (ca. 1520, cited in an 1881 issue of Notes and Queries:
He rolleth in his recordes,/ He sayeth, How saye ye my lordes?/ Is nat my reason good?/ Good euyn, good Robyn Hood!/ Some say yes, and some/Syt styll as they were dom:/ Thus thwartyng ouer thom [that is, thumb],/ He ruleth all the roste/ With braggynge and with bost;/ Born vp on euery syde/ With pompe and with pryde,/ With, trompe vp, alleluya!
That same 1881 volume of Notes and Queries includes a reference to Debate of the Carpenter's Tools (late 15th century). In the version reported in James Halliwell-Phillipps, *A Dictionary of Archaic and Provincial Words, Obsolete Phrases, * (1921), the lines run as follows:
Ye, than seyd the rewle-stone,/Mayster hath many fone:/And ye wold helpe at his nede./My mayster schuld the better spede,/But whatsoever ye brage our boste,/My mayster yet shall reule the roste.
The trouble with all of these early instances is that they could be read as referring to ruling the roost (the roosting-rod in a poultry house) or to ruling the roast (the meat to be carved by the person sitting at the head of the table). So the unanswered question about these early instances is whether roste/rost eventually resolved into roost, roast, or both.
Emergence of 'rule the roast'
The earliest instance of "rule the roast" that I've been able to find is from W.S., The Puritaine, or The Widdow of Watling-street (1607):
Edmond. So a faire riddance, my fathers layde in dust his Coffin and he is like a whole-meate-pye, and the wormes will cut him vp shortlie ; farewell old Dad, farewell. ... Why al the world knowes as long as twas his pleasure to get me, twas his duety to get for me : I know the law in that point no Atturney can gull me ; Well, my Vncle is an olde Asse, and an Admirable Cockscombe, Ile rule the Roast my selfe, Ile be kept vnder no more , I know what I may do well inough by my Fathers Copy : the Lawe's in mine owne hands now : nay now I know my strength, Ile be strong inough for my Mother I warrant you?
From Richard Sheldon, “The Hereticall Rule of the Romane Faith” in The Motives of Richard Sheldon Pr for his iust, voluntary, and free renouncing of Communion with the Bishop of Rome (1612):
I ask, whether the gates of hell preuailed not against this [Pope] John [10 or 11]? Who as a Baronius himself acknowledgeth, was exalted into the Apostolicall chaire, by the meanes of the impudent strumpet Theodora; with whom also he liued most impurely in the time of his Papacie (or shall I fay rather her Papacie, shee ruling the roast) for which cause by the Cardinall himself this John is worthily reputed for a false high Bishop, an Apostata, an Intruder, and a most iniust possessour of the Apostolicall See.
From M.N., Remaines Concerning Brittaine (1629):
William, Marques of Winchester, being asked how he continued of the Councell in the troublesome times of diuers Princes ; answered, By being a Willow, and not an Oake. Hee would also often say, that hee found great ease in this : That I neuer sought to rule the roast, and to be the director of others, but always suffered my selfe to be swayed with the most and mightiest. [The 1637 version of Remaines Concerning Britain repeats this anecdote, but with the word roste in place of roast.]
And from Thomas Nabbs, Microcosmus (1637, in a 1780 edition):
Tasting. Tasting, mine [name], sir. I am my lady’s cook, and king of the kitchen ; where I rule the roast, command imperiously, and am a very tyrant in my office.
The first clear instances of 'rule the roost'
In its modern spelling "rule the roost" did not definitely appear (as far as I've been able to tell) until the 1820s. From a review of J. Bee, A Living Picture of London for 1828, in The Monthly Review (May 1828):
But, whatever the bulk of the people may be found in any of the provincial cities, under similar circumstances, the population of London is in a superior degree ; or, say baser, if the purpose be a bad one, as rioting, or the attempts of a mobocracy to rule the roost. An election he considers the highest state of excitement to which the public mind can be brought.
And from Lydia Child, A New Flower for Children (1856):
'Sir Naked-legs,' said I [a rooster], 'it is none of your business.'
'I expect to rule the roost here,' said he [another rooster].
'That you may do and welcome,' said I. 'The farm is large enough for us both; and I can pick up my own grasshoppers.' I was determined not to fight the foolish little chap.
There is in fact a much earlier reported instance of "rule the roost," from Thomas Randolph, The Muse’s Looking-Glass (1638), but regrettably I can't find a copy of that work from the seventeenth century. Instead, it is simply reported in an 1875 edition and picked up in 1882 by A. Smythe Palmer, Folk-Etymology, as follows:
Bird. Ay, this is he we look'd for all the while!/ Scurrility, here she hath her impious throne,/ Here lies her heathenish dominion,/ In this most impious cell of corruption;/ For 'tis a purgatory, a mere limbo,/ Where the black devil and his dam Scurrility/ Do rule the roost, foul princes of the air!
But did Randolph originally use the spelling roost? In my experience subsequent editors have been all too ready to replace the ambiguous roste or rost with their preferred modern word roast or roost.
Past discussions of 'roast' vs. 'roost'
I conclude this not very satisfactory answer with citations to a few early attempts to resolve the roast versus roost question.
From Charles Richardson, A New Dictionary of the English Language (1839):
To rule the roast, (sc.) as king of the feast, orderer, purveyor, president ; or may it not be to rule the roost, an expression of which every poultry-yard would supply an explanation?
Multiple "Replies" at various dates in Notes and Queries (1881, pages 127, 169–71, 277–78, 396–97, 432–33, 477, 495, and 512) wrestle with the question. One writer notes that both rost (roosting pole) and rost (spit for cooking meat) refer to a rod, which in turn may symbolize power in a ruler’s hand. Thus: "This year sall richt and reason rule the rod." [New Year’s Gift to Q. Mary in Evergreen.] Another argues that Skelton uses rost for roast and roste for roost. A third argues that rost/roste in the phrase originally signified rostrum.
Some early citations in these Notes and Queries arguments are the ones from Debate of the Carpenter’s Tools [by 1500] and Skelton's Colin Clout [ca. 1518] cited earlier in this answer, but in the latter case given in slightly different wording: "But at the playsure of one/That ruleth the roste alone." (On the other hand, Skelton, "Eleanor Rumming" [unspecified date?] has "The hens run in the mashfat,/For the go to roust/Straight over the ale ioust." and [Author unknown?], “Lybeaus Disconus” [?] has "I here greét bost,/And fer smelle rost." If we could count on consistent spelling—which we can't—we might conclude that in Skelton's day roust = roost but rost/roste = roast.) Also, from a Caxton printing of Polycronicon : "Meotydes sente a letter to Alysaunder in this manner yf goddess wolde that the hauynge of thy bodye were euen to the coueyteyse of thy soule/ the worlde mygghte not receyue the/ whether thou knowe not that threes that growe longe tymed be rosted in a lytaell whyle/ than take hede and beware that thou falle not with the tree whyle thou takest to ye bowes." (However, a later reply, pointing to the original Latin and to another translation, argues that "Caxton’s rosted is a misprint for rooted." But yet another Notes and Queries reply observes that the 1482 Caxton printing has not rosted but roted: "whether thou knowe not that trees that grow long tyme be roted up in a litel while.")
Also, Hall, Union : "Thou, duke of Burgoyn, ruled the rost, and governed both king Charles ... and his whole realme." Andrew Kingesmyl, A most Excellent and Comfortable Treatise for all such as are in any Maner of Way either troubled in Mynd or afflicted in Bodie : "Let us not look here to rule the roste, but to be rosted rather of Rulers." N. Breton, "Countesse of Pembroke’s Love" : "Where care and sorrow, death, and deadly strife,/Doe rule the rost, in this accursed life." Joshua Sylvester, "Job Triumphant in His Triall" [1616(?), but quoted from 1633 edition]: Would He [the Lord] seem to smile at Good men’s stripes among?/Would he bestow upon th' Ungodly-most/Earth’s Soveraintie, and let them rule the Rost? ... I sate as Chief, I only ruled the roast,/Dwelt as a King amid an armed Hoast." Earle, Microcosmographie : "In the kitchin he will domineer, and rule the roste, in spight of his master."
One Notes and Queries commenter (May 14, 1881, p. 397) makes this argument:
The poultry-yard has suggested the figure "he is cock of the walk," and it seems to me that he who is in this proud position will "rule the roost" also. I have, however, generally heard that "—— rules the roast." There is room for both forms, and precisians may use one when the ruler is masculine and the other when the presiding genius is feminine. A man rules—as a rule—"the roost," his household, but in ninety-nine cases out of a hundred it is a woman who rules "the roast."
It seems abundantly clear that "rule the roast" (with appearances from the early 1600s forward) was popular in English before "rule the roost" (with appearances from the early 1800s forward) was. But it is also clear that "rule the rost/roste" was popular in English before versions of the expression containing either roast or roost appeared. And the early rost/roste instances strike me as being quite ambiguous. Indeed, it is not impossible that the popular understanding of the expression may have flipped more than once—from (in effect) "rule the rod" to "rule the roast" to "rule the roost," for example.
I haven't been able to nail down what the original sense of "rule the rost/roste" was, but I can say that the expression goes back a long way—to 1500 at least.