Banbury Story of a Cock and a Bull: A roundabout, nonsensical story.
--The 1811 Dictionary of the Vulgar Tongue, by Francis Grose (1811).
This is a quite mysterious phrase, and appears to be the conjunction of two different idioms. Cock has long been used to refer to one who brags and swaggers, and bull for trifling or deceptive talk, and this is recognizably related to our modern cock and bull story -- at the least, it certainly helped to guide it into its current form.
'Banbury story' is perhaps the more interesting part of the phrase. It was once a popular, stand-alone idiom meaning a nonsensical or untrue story, but it has sadly died out. Banbury, a town in Oxfordshire was, from (very approximately) the 1500s to the 1700s, perhaps the most abused place in England. A Banbury-wife was a whore, a Banbury-gloss was a misleading interpretation, Banbury-cheese was weak cheese, or, by extension, anything not up to snuff. If you wanted a fool for your story, you used a Banbury tinker (stupid and poor) or the Mayor of Banbury (wrongheaded and full of himself). A 'Banbury man' was a term for a hypocrite... unless he was needed for another role.
A Banbury man will hang his cat on a Monday for catching mice on a Sunday.
This flood of disdain was said to be because the Banburians were zealous Puritans, but of course, this does not explain the foolish tinkers or the handiness of prostitutes. It appears that 'Banbury-glosses' (c. 1530) was the predecessor to the 'Banbury story', and 'Banbury story' was expanded into "Banbury Story of a Cock and a Bull" as a matter of emphasis, although that leaves the mystery of why "a cock" and "a bull", as that would appear to indicate a story about the actual animals.
Regardless, in the 1700s it became more and more popular to hate the Dutch (cf. Dutch courage, Dutch uncle, Dutch Talent, Dutch Treat), and by the mid-1800s Banbury was redundant -- there was a new idiot neighbor, and now even the Banburians could join in on hurling the abuse.