Michael Quinion, a well-known etymologist of such phrases, also offers the story given in Panic Button's answer above and then adds...
"Another story, undated but usually taken to refer to events of a similar period, is that Coventry was strongly opposed to having troops billeted on townspeople, and that soldiers sent there were ostracised by the local population. Take your pick. My own feeling is that neither is convincing, not least because of the century-long gap between Civil War events and the first appearance of the idiom — not impossible, though."
As you see, he's not too happy with either tale and the Lady Godiva version sounds even more improbable. Perhaps best to answer, "Nobody's very sure!"