I've been running a home-brew campaign for about 5 years now, and the characters are isolated from most of the rest of the world. They don't have too much access to magic, or extra spells, or any of the usual stuff. I gave everyone a bonus feat at 7th and 13th level, and used a 40-point-buy system to toughen them up out of the gate (I also use a hit point system that gives a few more hit points than average).
So, I haven't used a "feat at every level" system, but I have added extra feats, and I figured I'd chime in with my experiences.
First, adding extra feats doesn't do much to game balance--unless you let it. I was afraid of some of the problems that have been mentioned (getting certain other feats too soon, getting prestige classes too soon, etc.). I figured that those things had been designed to not be available early on purpose and I didn't want to mess with that. My solution was to restrict the available bonus feats at 7th and 13th levels.
And, if I were to do a feat-at-every-level game, I'd probably do the same. I'd probably make a few lists of feats and tell my players something like:
1) You can take any feat you qualify for at the usual progression (i.e. every 3rd)
2) You can take any feat from list A at the remaining odd levels
3) You can take any feat from list B at the remaining even levels
Then I'd make up the lists of feats (trying to maintain some level of balance that cohered with the existing limits) and let them play. List A might include the saving throw feats, Run, Endurance, stuff that could be very flavorful but not necessarily over-powering in combat. List B might include all the fighter and magic feats.
Just a thought.
Dave