The story
Formed of herd + cat, perhaps in reference to domesticated cats’ solitary nature. Possibly from the opening scene of Monty Python's Life of Brian (1979). Shepherds are discussing sheep and the topic strays to cats: "Can you imagine a herds of cats waiting to be sheared? Meow! Meow! Woo hoo hoo." Earliest usage unknown, but the idiom is attested from the 1980s.
Etymology from Wiktionary, CC BY-SA 4.0.