Looking at Google Books, I see proto-figurative uses of "for the birds" along the lines of:
By sword and famine shall they be consumed that their carcase may become food for the birds of the heavens and the beast of the earth
The implication here (and in several other similar cases) is not that the birds are feeding on horse shit, but rather on the dead bodies of those deemed unworthy of living.
There are also many references to passages such as Matthew 6:26:
Behold the fowls of the air: for they sow not, neither do they reap, nor gather into barns; yet your heavenly Father feedeth them. Are ye not much better than they?
These passages imply that birds are among the lowliest of all of God's creations, and thus anything that is "for the birds" would be lower than the lowest.
I'll also mention The Birds by Aristophanes, which contains at a very minimum, dozens of references to birds which could somehow apply (though I'll admit I've made no attempt to penetrate this work sufficiently to speculate how it might apply).
In my (admittedly brief) review of works up into the 70s, I did not see any direct uses of the figurative "for the birds" until 1960, and nowhere did I see a use which implied the birds were feeding on horse shit. (But of late Ngram "hits" in the early/mid 1900s have been severely hampered by the limitations imposed on displaying them, sorry to say.)
In my opinion (and I've seen nothing to contradict it, but lots of birds supporting the notion), it's most reasonable to regard "for the birds" as simply reflecting the fact that birds will feed on very tiny amounts of pretty much anything. (Consider, eg, the idiom chicken feed meaning "a trivial amount of money.) It's the sort of expression that would be invented tomorrow if it didn't already exist.