Although way off base on the specifics, a number of pre-Socratic philosophers already raised the idea that one type of organism could descend from another type. Aristotle hinted at the possibility as well. Unfortunately, later interpretations of Aristotelianism - alongside Platonism, which was even worse in this regard - were more fixed on the specific notion that all natural things are actualisations of abstract universals. (So every cat is an actualisation of the universal idea "cat".) A consequence of this thinking was that it led to an overly teleological view of the world, where every thing has a fixed purpose. This became a tenet of Christian philosophy later on.
Aristotle himself did not claim that organisms always had to correspond to some fixed universal (Plato, contrarily, did claim that), and argued that there wasn't some kind of "Idea-realm" of which our own world is but a mere shadow. Instead, Aristotle reasoned that the universal essence of all things is within them, and that there is no separate realm of ideas". Rather, every cat simply contains a certain "catness", a "cat-essence", if you will. On these grounds Aristotle's actual ideas did allow for that essence to change... to evolve. Unfortunately, that interpretation was later discarded by Aristotelians, and particularly by medieval neo-Aristotelians (who were, via earlier Christian philosophy, clearly influenced by Platonism).
So... kill of Platonism altogether, or have Aristotle's ideas on the subject interpreted in a less "Platonist" way, and I'd say the philosophical basis for evolutionary thought is right there. Waiting for someone to start really thinking about it. Farmers have known for millennia that crossbreeding of animals and plants can favour certain traits, of course. And something like Gregor Mendel's experiments could be carried out in Antiquity, I'd say. Given the above scenario and a lot of luck, you could have a rudimentary theory of natural selection worked out in Antiquity.