I would love to know the origin of this saying.
The OED gives the first citation of the phrase from Leon Uris, "Battle Cry" in 1953 (but if it appeared in print then, it would certainly have been around for a while before that. They also give a possibly related phrase "don't give a dead rat" from Mark Twain, "The Adventures of Huckleberry Finn" (1884).
COHA (Corpus of Historical American English) has its first instance in 1967.
If you're asking about how it came to be used, I think it is often futile to look for a particular story in the inventive ways that people use words - especially imprecations.
Apart from a single occurrence in 1953 (see Colin’s answer), Google ngram sees it picking up from 1970, after sporadic use in the 60’s. I don't know anything about where it comes from, but it was probably picked up more for how it rolls of the tongue than other reasons.
An earlier phrase or progenitor was "you bet your sweet patootie." Now, with that in mind, consider this citation:
"Say, Dan, I want you to take a slant at my gal's photos--you ain't seen 'em yet, have ya?--she's some sweet patootie." Ibid., 13 January 1919.
Commentary here from the American Dialect Archives suggests that "patoot" and "patootie" refer to "potato," and the earlier uses are diminutives. That is, a trifle. Patootie is taking on the meaning of "rear end" by the late '30s, and somewhere between there and the '60s we have the emergence of "I don't give a horse's patootie," where patootie is an obvious euphemism.
Ergo, "I don't give a rat's ass" is a humorous back-formation of the same idea, made a bit punchier for effect. "I don't give a flying f_ck" is common by the early '70s and the construction is a common trope.