Some early birds, in the hand and out
Here are a few other early birds in the hand and out, not noted in Mari-Lou A's excellent answer, uncovered by searches at Early English Books Online.
From Wynhyn de Worde, The Parlyament of Byrdes (circa 1520):
"I saye," quod the tydyffre, "we Kentysshe men, / We maye not gyue the crowe a pen, / For with them that are not sober and good, / A byrde in hande is worthe two in the wood."
Mari-Lou A notes in a comment below that the proverb expressed in this first quotation "is the English translation of the Latin Plus valet in manibus avis unica quam dupla silvis—'silvis' meaning 'wood(s)' aka sylvan." Thanks very much for pointing that out, Mari-Lou A!
From Hugh Rhodes, The Boke of Nurtur for Men Seruauntes, and Children with Stans puer ad mensam, Newelye Corrected, Verye Vtyle and Necessarye vnto All Youth (1560[?]):
•aughe not to muche, ynoughe is a treasure / •uche laughinge men say lacketh n•rture / •o sad is not be•t, the meane is aduauntage / ••rth for policie somtime, is w•sedom & no outrage / •r ye begyn marke the ende, and take good hede / • good forethought is a frende at nede / •e not hasty thyne aunswere to make / •east thou repent after, when it is to late. / •et or thou spende, then byd thy frynde good morow / •a•e payne, and auoyde sorowe. / [A] byrde in hande, is worth ten at large, / In all my lyfe I coulde scant fynde one trustre / Fynde a frende, than proue hym, that thou wylt truste to, / So shalt thou knowe, what he wyll do.
From Thomas Blague, A Schole of Wise Conceytes Wherein as Euery Conceyte Hath Wit, So the Most Haue Much Mirth (1569):
Of the Fisher and the litle fishe.
A Fisher cast his hookes into the water bayted wyth fleshe, wherewith he caught a litle fish, the prisoner besoughte him to release him, now being so little, and to lette hym growe bygger, that héereafter hée might haue the more commoditie of him: Nay sayde the Fisher, I wil not bye the pigge in the poke, for I vse too take what presently I can get.
MOR[AL]. Leaue not the bird in the hand, for that in the bushe.
From John Florio, Florio His Firste Fruites Which Yeelde Familiar Speech, Merie Prouerbes, Wittie Sentences, and Golden Sayings (1578):
Ʋn vcello in gabbia, ne val due del bosco, & pure si é meglio esser vcello di campagna, che vcello di gabbia.
One byrd in the hand, is worth two in the forest, and yet it is better to be a bird of the field, then a byrd of the cage.
From Thomas Proctor, A Gorgious Gallery, of Gallant Inuentions Garnished and Decked with Diuers Dayntie Deuises, Right Delicate and Delightfull, to Recreate Eche Modest Minde Withall (1578):
Thou doost well vnderstand / These wordes not spoken seilde / More suer a birde in hand, / Then twenty in the feild. / Thou knowest thine owne sure band / And how that it hath helde / Then chaunge it for no new: / But loue him that is trew.
From H.C., The Forrest of Fancy Wherein Is Conteined Very Prety Apothegmes, and Pleasaunt Histories, Both in Meeter and Prose, Songes, Sonets, Epigrams and Epistles, of Diuerse Matter and in Diuerse Manner (1579):
Surelye my Sulippo, when I remember the poore estate wherin thou presently standest, and cōpare it with the misery of this our age, I cannot but greatlye maruaile to see thy slacknesse in seeking preferment cōsidering how hard a time it is to attain to any thing, or to kepe y• which wee haue with quietnesse, euerye one beeing readye to pull the meate out of an other mans mouth, that happy is he who hath any thing to stay vnto, for if he want he shall finde few friendes in his necessity that will pittie his pouertie or set to their handes to helpe him, be his neede neuer so great, and therefore in my poore opinion, it is good (as they say) to hold open the poke whilst the pigge is profered, and taking the time whilst it serueth, to stryke whilst the yron is hote, and not with Esopes Dogge, leauing the fleshe for the shadow, forgoe a thing certayne, for a hope vncertaine, least repentaunce follow, when it is to late, for better it is to haue one byrde in hande, then two in the Bushe, seeing that often times whilste the Gratie growes the steede starues, for hee that hopeth after deade mén shoes many times goeth barefoote many things happen betweene the cuppe and the lippe, and therefore diuerse meanes there may be hereafter to hinder that which may now without any great difficultie, be atchieued seeing there is nothing but onely the wante of mayster Moliscus good will, to preuent your purpose, which by good perswation and earnest intreaty, may possibly be obteined the rather or yt he seeth mayster Glomerok so desyrous to doe you good, ...
From Flowres or Eloquent Phrases of the Latine Speach, Gathered ont [sic] of Al the Sixe Comœdies of Terence (translation published in 1581):
Ego spem pretio non emo, I will not geue a bird in the hand for two in the wood, I wil not buy the pig in the poke.
From Thomas Lodge, Euphues Golden Legacie Found After His Death in His Cell at Silexedra (1592):
How say you by this Item Forrester, (quoth Ganimede) the faire shepheardesse fauours you, who is mistresse of so many flockes. Leaue of man the supposition of Rosalynds loue, when as watching at her, you roue beyond the Moone, and cast your lookes vpon my mistresse, who no doubt is as faire though not so royall, one bird in the hand is worth two in the wood: better possesse the loue of Aliena, then catch frinously at the shadowe of Rosalynd.
From Anthonie Fletcher, Certaine Very Proper, and Most Profitable Similies Wherein Sundrie, and Very Many, Most Foule Vices, and Dangerous Sinnes, of All Sorts, Are So Plainly Laid Open, and Displaied in Their Kindes, and So Pointed at with the Finger of God, ... (1595):
But when he hath sounded thée to the depth, and perceiueth that thou hast an house, a lease, good furniture, some land, plate, or other cōmoditie, then he wil tel thée, that he would faine do thée good, and helpe thée, but the world is dangerous, and that a birde in his hand is better then two in the wood, and his money is his plough, and that he must liue vpon it, as the husbandman liueth vpon his plough.
From The Philosophie, Commonlie Called, the Morals Written by the Learned Philosopher Plutarch of Chæronea (translation published in 1603):
The poore prisoner taking hold presently of this aenigmaticall and darke speech, and thinking (as I suppose) that one bird in hand is better than two in bush, and according to the common saying, that
A foole is he who leaving that which readie is and sure,
Doth follow after things that be unreadie and unsure.
made choise of saving his life by the surer way, rather than by the juster meanes; for he discovered unto Nero that which the man had whispered secretly unto him: whereupon presently the partie was apprehended and carried away to the place of torture, where by racking, scortching and scourging; he was urged miserable wretch, to confesse and speake out that perforce, which of himselfe he had revealed without any constraint at all.
Early ratios of oak tree feet and wits fore and aft
Also of possible interest are these early alternative instances in which one of one kind is worth two of another. From John Fitzherbert, Here Begynneth a Newe Tracte or Treatyse Moost P[ro]fytable for all Husba[n]de Men and Very Frutefull for All Other Persones to Rede (1530):
And yf there be any okes bothe great and small / fell them and pyll them / and sell the barke by it selfe / and than sort the trees / the polles by them selfe / ye myddell sort by them selfe / & the greatest by thē selfe / & than sell them by scores or halfe scores or hondredes / as thou mayst / and to fell it harde by ye erth / for one fote nexte to the erthe is worth two fote in the toppe / and to cutte thy tymber longe ynoughe that thou leue no tymber in the toppe.
And from Robert Greene, Mamillia A Mirrour or Looking-Glasse for the Ladies of Englande (1583):
Yea but the Mariners sound at the first, for feare of a rocke: the surgion searcheth betimes, for his surest proofe: one forewit is worth two after: it is good to beware, when the acte is done too late commeth repentance.
Conclusions
The earliest example I found asserting (in less modern English) that "a bird in the hand is worth two in the wood" is from 1520 in The Parlyament of Birds. This instance is 26 years earlier than the contrary instance in John Heywood, A Dialogue Conteinyng the Nomber in Effect of all the Prouerbes in the Englishe Tongue Compacte in a Matter Concernyng two Maner of Mariages (1546), cited in the posted question:
I thanke you (quoth I) but great boste & smal roste, / Maketh vnsauery mouthes, where euer men oste. / And this boste veraie vnsauourly serueth. / For while the grasse groweth, the horse sterueth. / Better one byrde in hande than ten in the wood. / Rome was not bylt on a daie (quoth he) & yet stood / Tyll it was fynysht, as some saie, full fayre.
Early English Books Online didn't find any matches for "three in the wood" or "three in the bush," notwithstanding the very old instances of that variant noted in the posted question. In any event, whether or not "two in the wood [or bush]" was the original comparison to "a bird in the hand," it seems to have been firmly established as the most popular numerical form of the expression by 1600.
UPDATE (September 13, 2019): Instances from 1509 and earlier
Bartlett Whiting, Proverbs, Sentences, and Proverbial Phrases from English Writings Mainly Before 1500 (1968) cites six relevant instances of variants on the phrase from circa 1450 to 1509:
A Bird in the hand is better than two in the wood (varied)
c1450 Capgrave [The life of St.] Katharine [of Alexandria] 93-5.250–2: It is more sekyr a byrd in your fest Than to have three in the sky a-bove, And more profitable to youre be-hove. c1470 Harley MS.3362 f.4a in Retrospective 309{29}: Betyr ys a byrd in the hond, than tweye in the wode. c1475 Rawlinson MS. D 328 119.27: Hyt ys better a byrd in hon than iiij with-owyt. a1500 Additional MS.37075 278.17: Better (MS beeter) ys the byrd yn hond than ij in the wodde. a1500 Hill 128.6: A birde in hond is better than thre in the wode. 1509 Barclay [The] Ship [of Fools] II 74{3–4}: Better have one birde sure within thy wall Or fast in a Cage than twenty score without.
In ascending order by date, these instances give the number of birds not in the hand as three (circa 1450), two ["tweye"] (circa 1470), four ["iiij"] (circa 1475), two ["ij"] ("a1500), three ["thre"] (a1500), and 400 ["twenty score"] (1509). I don't know whether Whiting uses the term "a1500" to signify "as of 1500," "after 1500," or something else.)
Clearly, in the early days of the expression, the face value of a bird held securely in the hand ranged considerably—from 2 to 400 birds moving about freely.