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.
> [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.