The Oxford English Dictionary traces singular they back to 1375, where it appears in the medieval romance William and the Werewolf. Except for the old-style language of that poem, its use of singular they to refer to an unnamed person seems very modern. Here’s the Middle English version: ‘Hastely hiȝed eche . . . þei neyȝþed so neiȝh . . . þere william & his worþi lef were liand i-fere.’ In modern English, that’s: ‘Each man hurried . . . till they drew near . . . where William and his darling were lying together.’
Since forms may exist in speech long before they’re written down, it’s likely that singular they was common even before the late fourteenth century. That makes an old form even older.
There's a few more examples in the free OED entries for they and their, and even more in the MED under they 1a(e). (These are both well-regarded sources on historical English, with the OED often being regarded as the best.)
As for how common it was, there's no definitive answer. In The Rise of Epicene They, the author did a proximity search for pronouns following "each/every [noun]" (or similar) in The Canterbury Tales, and found that 18% of the time the pronoun that followed was "they", arguing that this is a good measure for English at the time and place it was written (early 15th century, or earlier if the scribe was faithful to the version being copied).
When did the prohibitions on singular they begin? Androcentrism in Prescriptive Grammar cites a 1746 grammar rule, which it says is "best viewed as an unusually early and very incipient form of the attack on singular 'they", and quotes another source from 1795 that calls out singular they as one of "many violations".
(Singular they isn't one grammatical feature; it is many. There is diversity in when each came into use, but this answer mainly provides evidence for one or two types. I will expand on the other types if I find a suitable source.)
Care would need to be taken in certain passages since the Wycliffe is translated from the Latin Vulgate whereas the KJV is translated from the Koine Greek text and the Masoretic Hebrew text but in these two examples above, the sense is the same, despite different source texts, and the comparison is valid in English.
The Oxford English Dictionary has traced the singular 'they' back to 1375 and 1450 but this does not suggest that it was common usage, only that it is seen in example:
a. With an antecedent that is grammatically singular, but refers collectively to the members of a group, or has universal reference (e.g. each person, everyone, nobody).
Sometimes, but not always, used to avoid having to specify the gender(s) of the individual(s) being referred to; cf. sense A. 2b.
a1375 (▸c1350) William of Palerne (1867) l. 2179 Hastely hiȝed eche wiȝt..til þei neyȝþed so neiȝh..þere william & his worþi lef were liand i-fere.
c1450 (▸?c1400) Three Kings Cologne (Cambr. Ee.4.32) (1886) 6 Noman was hardy in all þat countrey to sette aȝens hem, for drede þat þey hadde of hem.