As a matter of philosophy I don't like having NPCs follow different rules. At least not important NPCs. I do agree that players should be special, or else their survival and success would just be a matter of luck. The difference here is optimisation. A PC should be optimised, an NPC only in an exceptional case.
Then give them unoptimized feats for the extra ones - that shouldn't take long.
I already have a comparatively cheap way of gaining basic feats in the item rules: Want Power Attack for your wizard gish? Put it on an item.
I actually don't like this rule too much, because these items are unaccessible for low- to mid-level characters (when 10k is a lot) which need extra feats the most, whereas a level 20 character will buy himself tons of feats that way.
That cheapens the Fighter even more at high levels...
If I were to change the feat rules, they would have to count for everybody, even monsters.
Sure, see above. If monsters don't need to be optimized, extra feats are no biggie.
I also think the age-XP system alleviates a lot of problems with not gaining feats early on: Simply because most people don't stay lvl 1 or even lvl 4 for very long. A thirty-year old human is already lvl 6.
Approach this from the PCs' perspective : it means campaigns have to start at level 6 or above. It's fine if you don't especially care about lower levels but then you should perhaps mention it somewhere.
And if everyone were to get a feat every even level, a Fighter would have to get a feat EVERY level.
Some homebrew variants do that. Another option is to give them extra bonuses when they take a feat - I remember Khan suggesting something along those lines (tactical feats can be mined for ideas) - or make the feats scale for them.
There are feats that annoy me: Weapon Proficiencies for instance. Why do you need EWP for a Bastard Sword? Or a Katana? But these are already adressed in regional proficiencies (which I'd probably allow upon request). Alternatively I could rework the weapon. Bastard Swords and Katanas, as well as a number of other far eastern martial weapons should be simply martial weapons. Others not so clearly, but for those a racial proficiency bonus feat is in order. EWP should be limited to stuff like Kusari-gamas or spiked chains, which are really non-standard weapons, even in their place of origin.
I've seen it done with skill points, just like languages. I don't remember the details though.