Cette expression s'applique principalement à des choses (''Cette maison est vieille comme Hérode'').
Elle est citée par Furetière au XVIIe siècle, mais sa date d'apparition semble inconnue.

Contrairement à Mathusalem qui, lui, vécut "réellement" très vieux (969 ans, excusez du peu !), aucun des différents Hérode connus qui faisaient partie d'une dynastie de rois de Judée, n'a eu une extrême longévité.
Si le premier, Hérode Ier le Grand, a quand même vécu 69 ans, ce qui pour l'époque était une durée de vie rare, ce n'était quand même pas suffisant pour qu'il marque les siècles de cette manière.

Alors, soit c'est le cumul des règnes des 6 Hérode, qui se sont succédés de 73 avant J.C. jusqu'en l'an 93, qui a marqué les esprits au point de donner naissance à notre locution, soit il faut simplement la comprendre comme ''assez vieux pour remonter au temps d'Hérode''.