"exceed in any excess of evil," from Shakespeare's it out-Herods Herod in Hamlet's instruction to the players in "Hamlet" Act III, Scene II. Shakespeare used the same construction elsewhere ("All's Well that Ends Well" has out-villain'd villany). The phrase reflects the image of Herod as stock braggart and bully in old religious drama. The form of the phrase was widely imitated 19c. and extended to any excessive behavior.
Oh, it offends me to the soul to hear a robustious periwig-pated fellow tear a passion to tatters, to very rags, to split the ears of the groundlings, who for the most part are capable of nothing but inexplicable dumb-shows and noise: I would have such a fellow whipped for o'erdoing Termagant; it out-herods Herod: pray you, avoid it. ["Hamlet"]