Found this on 'The Straight Dope'

The more likely explanation, Word Detective ventures, is that the expression refers to old fables featuring talking animals, a notion that the French "cock to donkey" tends to corroborate. We've seen similar usages arise in our own time, leading me to think Word Detective has it right and that alternative theories are not just cock and bull stories but--dare I say it?--mickey mouse.

The Cock and Bull is a popular franchise of pubs down here where you can grab a steak and a pint o dark for lunch or dinner.