How Was "Feast" Pronounced in Early Modern English?
Solution 1:
TLDR: For John Donne, who was a contemporary of Shakespeare, it appears they weren't perfect rhymes, but good near-rhymes. Looking at what words John Donne rhymed with feast, guest, and rest, in his poetry, John Donne usually rhymed feast with beast, while he rhymed guest with words like breast, chest, possest, and rest, that we would think of rhyming today. However, he occasionally used a rhyme between these two sets of words, like beast and rest.
How were these words actually pronounced by Shakespeare? Guest had a short vowel in Middle English and has the same short vowel today, so it presumably was pronounced [gɛst]. Feast started out in Middle English with the long vowel [ɛː], but the Great Vowel Shift, which was well underway when Shakespeare wrote, raised [ɛː] to the value it has today, [iː]. So it would have been pronounced somewhere between these two, maybe as [feːst]. Since they were good near-rhymes, it seems unlikely that feast had the vowel it does today.
John Donne (1572—1631), who wrote his poems at approximately the same time as Shakespeare, rhymed feast with beast four times, and did not rhyme it with anything else.
And let his carrion coarse be a longer feast
To the Kings dogges, then any other beast.
The tables groane, as though this feast
Would, as the flood, destroy all fowle and beast.
You, and not only you, but all toyl'd beasts
Rest duly; at night all their toyles are dispensed;
But in their beds commenced
Are other labours, and more dainty feasts;
So may thy pastures with their flowery feasts,
As suddenly as Lard, fat thy leane beasts;
However, he rhymes beast with jest and rest, as well as feast.
We will not strive with Love that's a shee beaste;
But playinge wee are bounde, and yeald in Jest;
Can use his horse, goate, wolfe, and every beast,
And is not Asse himselfe to all the rest.
And looking at what Donne rhymes with guest, we have
That they did harbour Christ himself, a Guest,
Harbour these Hymns, to his dear name addrest.
this bowre vnfit for such a gueste,
but since she makes it now her Inn,
Would god twere like her sacred breast
most fayre without, most rich within.
TIS lost, to trust a Tombe with such a guest,
Or to confine her in a marble chest.
So, of a lone unhaunted place possest,
Did this soules second Inne, built by the guest,
This living buried man, this quiet mandrake, rest.
Looking at what he rhymes with rest, while he does rhyme it with beast, most of the time he rhymes rest with a word like best, blest, breast, devest, digest, possest, protest, west, which we would think of as rhyming in modern English.
From this, I would conclude feast did not rhyme with guest in Elizabethan English (at least, the variety that John Donne spoke), but was a good near-rhyme.
Solution 2:
I think it's most likely that feast had a long vowel and guest a short vowel, making this a near rhyme of [feːst] (or possibly [fɛːst]) and [gest].
Shakespeare seems to have sometimes used rhymes between words with slightly different e-like vowels
As evidence that Shakespeare sometimes rhymed words with similar rather than completely identical vowel sounds, consider the following rhymes:
Sonnet 132:
And truly not the morning sun of heaven 1840
Better becomes the grey cheeks of the east,
Nor that full star that ushers in the even
Doth half that glory to the sober west,
As those two mourning eyes become thy face:
The Passionate Pilgrim:
Lord, how mine eyes throw gazes to the east!
My heart doth charge the watch; the morning rise 195
Doth cite each moving sense from idle rest.
Not daring trust the office of mine eyes,
While Philomela sits and sings, I sit and mark,
And wish her lays were tuned like the lark;
The word east comes from an Old English word with a long diphthong ea (ēa in normalized spelling). The expected outcome in Middle English of this sound is the long vowel [ɛː], which in the course of Early Modern English developed a higher quality [eː] along the way to its usual present value of [iː]. In other words, the vowel in east was originally long, and outside of rhymes like these, there's no reason that I know of to suppose that Shakespeare spoke a dialect that shortened this vowel. (Shortening is possible in this context, not as a regular but as a sporadic sound change: breast is an example of a similar word where an originally long vowel was shortened.)
And on the other hand, west had an originally short vowel, and has a "short" vowel sound in Modern English, so it likely was short for Shakespeare as well: [west].
The simplest explanation of the above rhymes, and a number of others (such as the one that you are asking about), seems to be the hypothesis that a difference in vowel length was tolerated in Shakespeare's poetry between rhyming pairs. Although some people object to rhymes between words with anything other than identical vowels on aesthetic grounds, that is far from a firm basis for rejecting this possible analysis of Shakespeare's usage. Conventions for what makes a good rhyme differ between languages, eras, and authors: nobody alive today has access to Shakespeare's intuitions about rhyming, and it doesn't seem safe to say that we can substitute our own.
The vowel in feast
Of course, the modern English pronunciation of feast, /fiːst/, has a "long e" sound. Like the ea in east, this would correspond to the Middle English long vowel [ɛː] and Early Modern English long vowel [eː].
We do in fact have evidence that the word was pronounced with a long vowel in Middle English, in the form of spellings with ea and ee, two digraphs used in Middle English to represent the sound [ɛː].
The spelling fest(e) was also used in Middle English. Single e was used as a spelling of Middle English [ɛː], but is ambiguous in regards to vowel length: it also is used to represent the short vowel [e]. (The use of the macron (line above) diacritic to distinctively mark a vowel letter representing a long vowel sound is a modern convention; the spelling with "ē" mentioned in a comment was not used in Middle English manuscripts.)
Unlike east, the word feast does not go back to Old English. Feast was borrowed from French; the earliest citation in the Oxford English Dictionary (with the spelling feste) is labeled as from around 1200.
Why the vowel in feast is long, and how a short variant might exist
I think the most likely reason for the pronunciation of feast with a long vowel is because in some varieties of French, there was a sound change that lengthened vowels before /s/ (somewhat similar to the British English sound change lengthening /a/ to /ɑː/ in words like last). I think this sound change created a form [fɛːstə] in French that was taken into Middle English as [fɛːst(ə)].
However, I'm unfortunately not sure of the exact location in time and space of the French vowel-lengthening sound change. The Wikipedia article "Phonological history of French" lists "/a/ develops allophone [ɑ] before /s/" as a c. 1100 sound change but "lengthening of the preceding vowel" as a c. 1250–1300 sound change. The lengthening is treated in that article as part of the process of losing [s] before a consonant; however, since English feast has a pronounced [s] sound, it seems that the French loss of [s] in feste was obviously not complete at the time that feast entered English.
It may be possible that a form with a short vowel was also taken into English, either before the lengthening sound change occurred in French, or from a variety of French that did not undergo vowel lengthening.
There are words from French that are currently pronounced as monosyllables with a short vowel before st, such as jest, test, crest, pest, vest. However, most of these seem to be first attested later, not earlier, than the words that are currently pronounced with a long vowel (feast, beast), so I'm not completely sure what causes the divergence.
In the French spoken in Shakespeare's time, words like feste (the spelling then used in French) were pronounced without [s]; i.e. as [fɛːtə] (see A Dictionarie of the French and English Tongues, 1611, compiled by Randle Cotgrave, printed by Adam Islip, page 2). So Shakespeare's usage is presumably not based directly on the pronunciation of French during his lifetime.
The vowel in guest
Guest is a word with a fairly irregular development, mainly in terms of the initial consonant. The Oxford English Dictionary points out that the Old English form giest/gist/gyst/gæst should have developed to a present-day form starting with the palatal glide /j/; the velar /g/ could be due to Old Norse influence. Neither source is expected to yield a form with a long vowel in Modern English; however, the Oxford English Dictionary records a few Middle English spellings with digraphs for the vowel: geest and geast(e).
Given that Shakespeare also rhymes feast with best, you would need to assume lengthening in best as well to support the hypothesis that Shakespeare was using only perfect rhymes and had a long vowel in feast.
I would say the overall evidence for a possible long vowel in this word seems pretty slim, although it isn't entirely impossible (yeast shows an anomalously long vowel).
On apparent partial rhymes in Shakespeare, and whether they can all be explained away
I don't think it's possible to maintain that Shakespeare completely eschewed non-identical rhymes: there are rare examples of rhymes on clearly non-identical consonants, such as open/broken in Sonnet 61, which admits of no other plausible explanation.
However, when it's a matter of apparently non-identical vowels, other explanations are often plausible, due to the existence of sporadic vowel changes in the history of English (like the shortening in breast or lengthening in yeast mentioned above).
The main reason I think Shakespeare made use of rhymes between similar but non-identical rhymes is the number of examples where this seems to be the case: while each individual pair might be explained as an example of sporadic lengthening/shortening or dialectal variation, every additional example of rhymes between vowels of apparently different lengths (for the pair [eː]/[e] before [st], I know of at least three other examples: least, east, lease rhymed with possest, west, excesse) strengthens the case for viewing this as a situation where near-rhyming was permitted.
We also see Shakespeare rhyme French-derived words in -aste with words in -ast: there are at least two examples in Romeo and Juliet of haste/last ("O, let us hence; I stand on sudden haste. / Wisely and slow; they stumble that run fast." and "Therefore use none: let Romeo hence in haste / Else, when he's found, that hour is his last."), which I would interpret as a near-rhyme between [æːst] and [æst].
David Crystal reconstructs a perfect rhyme on a short vowel
However, it appears that David Crystal, who is well known for studying Shakespeare's pronunciation, considers Shakespeare to have had a short vowel in waste and taste ("Sounding Out Shakespeare: Sonnet Rhymes in Original Pronunciation", page 298). Per Greybeard's answer, Crystal also reconstructs a short vowel in feast.
Sources supporting near-rhyme between long and short vowel
"On Im/Pure Rhymes in Shakespeare’s Venus and Adonis", by Jerzy Wełna (Anglica 2016) discusses the issue of rhyme in Shakespeare's works and mentions this particular pair.
Regarding the general issue of e-rhymes in Shakespeare, Wełna writes "Rhymes in this group of words is a nightmare of phonologists". He points out that the rhymes matching feast and beast with words containing short vowels are also found in Middle English in Chaucer.
His conclusion is that "in cases like those in (10a) [this includes the rhyme feast/guest] it is safer to assume the presence of an imperfect rhyme so frequently found in traditional English poets instead of inventing pure rhymes on the basis of sounds produced through occasional changes usually occurring in non-standard varieties." (page 140)
Solution 3:
The Oxford Dictionary of Original Shakespearean Pronunciation by David Crystal (Perhaps behind a pay-wall) gives the Shakespearean/late-16th and early 17th century pronunciation of "feast" as "fest" as in festival.
It also gives "guest" as "gest" (hard g).