I’m aware of seven ways to change feats, but only three of them would definitely work for you:
The “floating” bonus feat of a 2nd-level chameleon, which requires 2 levels in chameleon, obviously.
Losing HD after you’ve qualified for and taken levels of the prestige class in question. Lycanthropy and reincarnate/ritual of vitality are the most rules-solid approaches to that.
Anyway, listed in the order I thought of them,
Player’s Handbook II retraining rules
You can swap a feat for any other feat you could have chosen at the time you chose the original feat. Does not explicitly require you to maintain requirements (unlike the rules for retraining class features), but the very first sentence describing retraining in general says
The most basic level of character revision is retraining—that is, adjusting a decision you made earlier in your character’s career by selecting a different legal option.
(Player’s Handbook II, pg. 192)
This emphasis, from the very outset, on retraining being a way to change one legal character into another legal character, strongly indicates that it is not a method to create a character that could not have been achieved through regular leveling up. That is, since you couldn’t have taken the 1st level of that prestige class without that requirement feat, you cannot use retraining to become a character with one-or-more levels in the prestige class but lacking that feat.
Retraining also explicitly states that the combination has to have been legal at the time you were making the original selection. That is, using a feat to, say, make something a class skill to improve your maximum rank in it to allow you to take a prestige class, and then retraining that feat to another feat now that the skill is a class skill because of the prestige class, is a no-go.
Psychic Reformation from Expanded Psionics Handbook
This is a 4th-level psion/wilder power that allows you to redo various choices you made in previous levels, explicitly including feats. Its text is shorter and less detailed than the Player’s Handbook II retraining section, but it does say this:
The subject must abide by the standard rules for selecting skills and feats, and so it cannot take feats for which it doesn’t qualify or take crossclass skills as class skills.
(Expanded Psionics Handbook, pg. 127)
This is a bit unclear, but I would take “the standard rules” to include the “legality” notion in Player’s Handbook II—that is, that you can’t use this to wind up with a character that couldn’t have naturally leveled up that way. But you could check with your DM.
Fiendish Codex I’s Embrace and Shun the Dark Chaos
You know this one: embrace the dark chaos lets you replace any feat with an Abyssal heritor feat, and shun the dark chaos allows you to replace an Abyssal heritor feat with any feat. As you indicated in the question, it explicitly prevents you from pulling requirements out from under other feats and prestige classes. Therefore, its primary form of abuse comes from swapping feats you didn’t have any choice in—notoriously, the four Martial Weapon Proficiency feats that an elf starts with—to things you actually want.
The “floating” bonus feat of chameleon 2nd, Races of Destiny
At 2nd level, chameleons get a bonus feat that they can change to any other bonus feat at the start of each day. Even better, for you, we have
You can’t use any abilities gained from your aptitude focus, ability boon, or mimic class feature abilities to qualify for a feat, prestige class, or other option. You can use your bonus feat to qualify for such options, but if you change the feat, you suffer the normal drawbacks for no longer meeting a prerequisite or requirement.
(Races of Destiny, pg. 112)
The “normal drawbacks for no longer meeting a [prestige class] requirement” are... none. There are no drawbacks once you’ve taken the 1st level of the class. There are exceptions—Book of Exalted Deeds, Complete Arcane, and Complete Warrior make all the prestige classes from those books lose class features if you lose their requirements—but for most prestige classes there aren’t.
The ancestral guidance of the Player’s Guide to Eberron revenant blade
Once per day, you can call upon your ancestors to grant you knowledge and talent beyond your normal aptitudes. To accomplish this, you must spend 1 hour in quiet meditation, starting at dawn. At the end of this hour, you gain a bonus feat selected from the list below; you need not meet the normal requirements for the feat. The feat lasts until dawn of the next day.
(Player’s Guide to Eberron, pg. 142)
which is good, but,
You can’t use this bonus feat to meet any requirements or prerequisites (such as for another feat or a prestige class).
(Player’s Guide to Eberron, pg. 142)
So that’s no good.
Gaining and losing HD
The idea here is that you gain some HD, use the feats (or other stats) of those HD to qualify for something, and then lose those HD (including the things they gave, e.g. feats) but keep the prestige class levels you gained while you had the HD.
You’ll often see level drain mentioned for this. But abusing level drain etc. doesn’t work, in my opinion, because the wording of the level-loss mechanics strongly implies that the level lost is the latest one, and this relies on being able to pick and choose earlier levels to lose out from under your prestige class levels. There is extremely little ground on which to claim that you can do that.
However, with lycanthropy, you explicitly lose the RHD of the base animal, not your latest HD. That means you can use those HD to qualify, and then lose those HD and not the levels in the prestige class. In theory, that base animal could be a battletitan (Monster Manual IV), with 36 HD and thus 12 feats, which is enough to qualify for almost anything.
Another approach that works is to use a race with RHD, and then change your race, e.g. with reincarnate or Savage Species’s ritual of vitality. The belgoi (Dungeon vol. 111) have 4 RHD as a Humanoid race, which makes them pretty easy to use with reincarnate. You can get a lot more than that with another type, but then your DM has to create a reincarnate table for that type—at that point, go with the ritual of vitality, which takes randomness out of the equation. (Realistically, you probably want ritual of vitality anyway.)
Pun-Pun can give—or remove—any ability, feat, effect, etc. he likes from himself. There are nearly zero limits on what Pun-Pun can or can’t do, or when he can or can’t do it. The only possible issue he might have is that maybe he is restricted to abilities and such that have actually been published—though, if we’re honest, with the way manipulate form is worded, he honestly probably doesn’t even have that limitation. Which ultimately makes this kind of rules abuse really pointless.