The issue that is really here is not whether feats/traits/whatever cover all three pillars or not. Why? Because it's not the pillars, but the game mechanic systems that these things will modify. And when you look at it that way, there currently is a major disparity between combat, exploration, and interaction.
Exploration? Right now in the game, the only system that deals with it is ability checks and the skill system.
Interaction? Same thing. Ability checks with the skill system.
But combat? Well, we're going to have the attack and defense system. The saving throw system. The initiative system. The arcane spell system. The divine spell system. The weapon system. The armor system. The speed and movement system. The Turn Undead system. Etc. etc. etc.
Why have feats traditionally all been about combat, and those few that were non-combat paled in comparison? There's your answer. There are many more game systems within D&D that involve combat, for which feats could be created to modify them.
So I believe there's no reason to split up the exploration and interaction pillars into two separate silos, at least as far as the skill/trait ideas were concerned... because there just aren't enough game systems in place to warrant it. The fact is... unless new game mechanics and system are put in place... BOTH interaction and roleplay are going to be covered by just the ability check and skill system... and thus, the only thing you really need to modify both of them are Traits.
So there real question is... which of our four "things" would grant you Traits as part of advancement? Race? Class? Background? Theme?
My personal opinion? Race and Background.
Of our four "things"... I think the split is fairly obvious. Class and Theme are about your combat abilities... Race and Background are about your skill, your personality, who you were, who you are, how people see and deal with you, and how you see and deal with the world. All the things the non-combat "Traits" would modify.
Just because you're a dwarf, doesn't mean you automatically should be more skilled using an axe or hammer. Just because you're an elf, shouldn't mean you automatically would lean to the longsword over another weapon. At least in my opinion. Leave Class to give you combat mechanics and Themes to grant you feats which affect those mechanics. Then have Background grant you skills and Race and Background grant you Traits which affect those Skills. Easy split. Easy to grant slots as you level up. Easy way to make things like your Race and Background matter over time.
At least, that's my feeling on the matter.