Have "choir" and "deer" ever rhymed?
Yes, the two words would have been pronounced with the same rhyme at around 1400 A.D.
The word deer is of Germanic origin (cf. German Tier). It was pronounced with a long, mid-high e-sound until the Great Vowel Shift raised the sound to a long, high i-sound, c. 1500.
[deːr] (pre-1500)
> [diːr] (Great Vowel Shift, after c. 1500)
The word choir is a, probably late twelfth century, borrowing from Old French. Originally pronounced with a French rounded front vowel, as evidenced by frequent spellings with oe, (1), the word was adapted to English pronunciation and hence pronounced with a long, mid-high e-sound, just as deer. This is suggested by common spellings with double-e, (2), and rhymes with words that definitenly had a long e vowel, (3).
(1) Tuelf other freres of the queor (c. 1300, St. Brendan)
(2) to governe þe queere (c. 1387, John Trevisa, Higden's Polychronicon)
(3) qweer : here : autere ('choir' : 'here' : 'altar') (c. 1440, John Capgrave's Life of Saint Norbert)
[kwøːr] (c. 1300)
> [kweːr] (c. 1400)
At some time before the onset of the Great Vowel Shift, the vowel in choir must have been raised from long e to i. The change is irregular and affected only a small number of words. The OED points out that the development "goes exactly with that of brere and frere to brier, friar." The spelling reflects this change as the word is frequently written with i, ie y, ye etc. from c. 1500 on, (4). The Great Vowel Shift, I would assume, then diphthongized the vowel, yielding more or less the modern pronunciation of the word. (The modern spelling with ch and oi is a later attempt at historicizing the word.)
(4) the whole quier (1553, Wilson's Arte of Rhetorique)
[kweːr] (c. 1400)
> [kwiːr] (irregular raising, pre-1500)
> [kwaɪr] (Great Vowel Shift, after c. 1500)
Hence, if the carol "The Holly and the Ivy" originates from Middle English, c. 1400, it originally featured perfect rhymes of deer and choir in [eː]. If it was written at the earliest stages of Early Modern English, c. 1500, it may have featured imperfect rhymes in [eː] and [iː]. If composed later, there were no ryhmes that would commonly feature in English poetry, [iː] and [aɪ].
It is not uncommon for traditional songs and fairy tales to be recorded substantially later than their original composition. Hence, the earliest known publication of the carol, c. 1710, does not offer evidence that the carol must have originated from that time as well. A closer examination of the lyrics may shed more light on when the carol was written. I looked at the text superficially and the archaic vocabulary and imagery of holly as Christ seem to me to be indeed compatible with an early date of composition.
Here is the entry for choir from our friends at Etymology Online:
choir (n.)
c. 1300, queor "part of the church where the choir sings," from Old French cuer, quer "(architectural) choir of a church; chorus of singers" (13c., Modern French choeur), from Latin chorus "choir" (see chorus). Meaning "band of singers" in English is from c. 1400, quyre. Re-spelled mid-17c. in an attempt to match classical forms, but the pronunciation has not changed.
Etymonline explicitly states that the shift in spelling from quyre to choir in the middle 1600s did not reflect a change in pronunciation, but it seems fair to ask whether there might not have been a shift in pronunciation between queor in 1300 and quyre in 1400, or a shift in pronunciation of quyre itself (with no change in spelling) between 1400 and the mid-1600s.
Nevertheless, these possibilities are moot if the song is not significantly more than 300 years old. According to the Wikipedia article on "The Holly and the Ivy," there is no firm evidence to push the date of the lyrics back before about 1711:
The words of the carol were included in Sylvester's 1861 collection A Garland of Christmas Carols where it is claimed to originate from "an old broadside, printed a century and a half since" [i.e. around 1711]: Husk's 1864 Songs of the Nativity also includes the carol, stating:
This carol appears to have nearly escaped the notice of collectors, as it has been reprinted by one alone, who states his copy to have been taken from "an old broadside, printed a century and a half since," i.e. about 1710. It is still retained on the broadsides printed at Birmingham.
As for the reference to "the running of the deer," a webpage dedicated to "Yule Songs" at the Proto-Indo-European Religion website has this comment:
The "running of the deer" in this song refers to the custom of going hunting in the forest on the day after the long night of the Winter Solstice. By Victorian times this had turned into a tradition of blasting away with a shotgun at as many birds as possible, including song birds, which were brought home and baked in meat pies. This became unacceptable and the tradition is now to participate in a Christmas Bird Count of which there are many organized versions.
I'm not sure what to make of the claimed lineage of Christmas bird counts, but the tradition of winter solstice hunting, if true, would explain why the lyricist associated "the running of the deer" with Christmas.
It's what's called a half-rhyme. Quoth Wikipedia:
Half rhyme or imperfect rhyme, sometimes called near-rhyme, lazy rhyme, or slant rhyme, is a type of rhyme formed by words with similar but not identical sounds. In most instances, either the vowel segments are different while the consonants are identical, or vice versa. This type of rhyme is also called approximate rhyme, inexact rhyme, imperfect rhyme (in contrast to perfect rhyme), off rhyme, analyzed rhyme, suspended rhyme, or sprung rhyme.
Wikipedia: Perfect and Imperfect Rhyme
Such rhymes often turn on the last consonant sound. The poems of Emily Dickinson contain numerous examples. (See "A Narrow Fellow in the grass," noting that the second and fourth lines in each stanza are half-rhymes.)
EL&U has a number of similar answers, albeit to differently framed questions.