For one, we need to consider which version of Quick Change we are talking about; it was printed in both Savage Species and Races of Eberron. Clearly, the master of flies is referring to the version that was published in the same book it was, and it’s unlikely that the team working on Races of Eberron was trying to replace it (they probably didn’t even know about it), but officially as the latest reprint, the Races of Eberron is “the” Quick Change.
If we go with that, then a changeling meets the requirements for Quick Change and for the special requirement for master of flies.
If we don’t go with that, then a changeling does not meet the requirements for Quick Change, but a hengeyokai from Oriental Adventures does. Other options are fairly painful; druid is probably best, since wild shape meets the requirement (requires 5th).
Either way, you also need 8 ranks in Knowledge (nature). That one is tricky; by default you attain that at 5th level, but that... can be beaten, though not easily.
The extremely poorly-considered Primary Contact feat from Cityscape can get you there one level early, since it gives you a bonus rank in a skill, but that means taking it at 4th level to get that benefit: there are few ways to do that.
One is the marshal class from Miniatures Handbook; unlike most classes that grant a bonus feat, when marshal grants Skill Focus (Diplomacy) at 1st level, it specifies that if you already have that feat, you get some other feat you qualify for instead. Well, that could be Primary Contact. So now we’re looking at Quick Change, Favored, Skill Focus (Diplomacy), and a level of marshal taken carefully at 4th level in order to start master of flies at 5th instead of 6th. Big investment, even for your generous rules, to accelerate things by only one level.
The other option is far, far cheesier. The inspire greatness bardic music gives you two pseudo-HD, which increases your skill rank maximum. If you then use psychic reformation or other method of re-allocating your skill ranks, you can take advantage of that higher limit, and when the music ends, you keep your skill ranks even though they would now be illegal. This costs nothing other than having or hiring a sufficiently high-level bard and a sufficiently high-level psion to help you. That gets us two levels earlier.
The two approaches can be combined. Psychic reformation can also be used in this case to take Primary Contact without the nonsense with the marshal. That could be done as early as 2nd level if you have enough feats, to start master of flies at 3rd.
So 3rd looks like a minimum, but of course it’s not. You can get even more cheesy with your early-entry optimization; at the extreme, you can just become Pun-pun and just grant yourself everything you need right at 1st. For that matter, you could also just grant yourself everything master of flies offers, while still at 1st. Without more explicit constraints, this kind of question is always going to be trivially “well, 1st, because you could always just be Pun-pun.”