It's way older than the United States
Euphemistically, this not-fish is ancient. In his improbably fascinating essay at World Wide Words, Michael Quinion puts its first English-language appearance around 1420 -- 72 years before Columbus sailed the (presumably herring-filled) ocean blue!
Red herring is the oft-omitted third wheel of the 15th-century phrase "neither fish, nor fowl", and, by the close of the 17th century, it'd gain real traction thanks to The Gentleman's Recreation, a treatise that schooled English lords on how to maximize their lordliness. In 1697, that included fishing, hunting, and, of course, fox-chasing.