Originally a compound of けれ (kere, not found in isolation; meaning roughly “be that as it may”) + ども (domo, conjunctive particle introducing a contrary condition).
The former kere part has multiple possible derivations:
The 已然形 (izenkei, “realis form”) suffix for classical -ku adjectives (modern -i adjectives)
The 已然形 (izenkei, “realis form”) suffix for classical negative supposition auxiliary verb まじ (maji)
The 已然形 (izenkei, “realis form”) of classical past recollective auxiliary verb けり (keri)
Auxiliary verb maji conjugates almost identically to a classical -ku adjective, so 1 and 2 above can be broadly viewed together. This theory is somewhat flawed, in that the regular realis form of classical -ku adjectives would be not -kere, but rather -kare (as the fusion of adverbial ending -ku + the realis form are of verb あるaru “to be”). There are historical examples of -ku + are fusing into -kere, but these appear to be restricted to early modern Japanese in the Kyoto area, while keredomo appears in the late middle Japanese period and was not restricted to Kyoto.
The realis form of past recollective auxiliary verb kere was likewise formed by fusion, combining ki with the realis form are of existence verb ある (aru). There are other documented examples of the diphthong ia changing into e, so the shift from ki + are to kere would not be unexpected. The ki element was either the past recollective auxiliary verb ki, or the continuative stem form ki of Old Japanese verb 来 (く, “to come”) (with the compound presumably meaning “having come to be, having come into being”). Compare Englishbe that as it may.
The latter domo part was itself originally a compound of ど (do, conjunctive particle introducing a contrary condition) + も (mo, “even, also”, particle). The do portion grammatically requires that the preceding conjugation be in the realis form, and this is indeed the form used for the preceding kere portion of keredomo.