Age of Empires III basically has a system like this already. You start at level 10, and when you create or join a game you can limit the levels of your opponents to within two, five, ten, twenty or unlimited.
If you win against another level ten, you might level up, but probably not. However, if you beat a level 50-60 (which I think was around the highest level), you would probably gain many, many levels.
So if you're better than all the other people of your current level, you'll quickly level up and leave them behind. If you are truly around level ten then you'll stay around there. Losing to someone of your own level didn't make you rank down as much as losing to someone a lot lower. So it was okay if you were playing and your skill level and had a 50% win record, because you would stay around that level and continue playing those who were your equals.
Each few levels had a different name. I believe 10 was Private, and then somewhere around 12 you moved to Corporal, 15-16 was Sergeant and 20 was Lieutenant or something like that.
I played for a few months with my friend and it worked out well. We didn't play too often, so we only got to around level 15-16. If we wanted a challenge we'd look for a level 19-20, who were always willing to fight someone who looked weaker than themselves, and if we wanted less of a challenge we'd join games with people our level or slightly lower. There was rarely any total noob stomping. N00b stomping barely contributed to your ranking too, so if you cared about your ranking, (which I guess noob stompers usually don't, they just want to win games) then it didn't pay to beat people way lower than you.
Also, two people could play on account. It would work okay if the two people are somewhere around the same skill level, you would just have a combined ranking. It would get a lot harder if you were very different skill levels.