Take a look at the d20 Mini-game, Omega World (I think it's dungeon #92 or something). When it designed it's NPCs, it "Streamlined" feats into their creation, so that it would say something like "1 in 4 NPCs at this point would have improved initiative, so all NPCs at this level would get a +1 to initiative").
Taking this a bit further, you create "feat paths" for various character types - the power attacker, the weapon specialist, the archer, the dodger, the skilled character, and so forth. You create what feats a character in that group would take (power attacker would take cleave, power attack, great cleave, maybe improved bull rush, etc...), and then you present them as a list of class abilities. Or, you could factor these feats into the character itself. Power attack wouldn't be a combat option, but would be "-1 to attack, +1 (or +2 with a two-handed weapon) to damage on melee attacks" every few levels or so. If you decide to do this, you need to let fighters choose at least two feat paths, while other classes get to choose one. Since I assume you want to limit the complexity that feats bring to the game, I'd suggest when developing feat paths that you stick to "invisible feats", or those that add a bonus to your character and can then be promptly forgotten (Iron will, weapon focus, weapon finesse, etc...). And don't be afraid to create abilities that could replace a feat choice that might seem a bit more powerful (+1 AC, for example, is better than dodge) - while they ARE more powerful, the fact that PCs cannot select custom-tailored feats to suit a power build more than makes up for it.
***
As for skills, why not just have each player say where their character hails from, and how they grew up? That will give you an idea of what skills that character knows, and you can play skill checks as a simple level check (1d20+character's level+relevant ability?) or something to see if they are successful. and do something to get replace the rogue....
Realize that if you get rid of skills, you're boosting the fighter and other low-skill classes, and severely damaging rogues, bards, rangers, and the like. You need to find some way to compensae for that loss.