Nothing can replace chomp. Outrage DD mence? Yea, he is good but not even close to chomp. Ok, with a Life Orb he has more attack than chomp after a SD, but with SR weak and some 100% counters, i'm unable to see mence getting dangerous like chomp.
I mean, Outrage mence is dangerous, but not counterless, and with SR weak, you can't bring him early game to reveal the opponent "counter" (because even without 100% counter, early game chomp can't sweep, maybe kill one mon, but he will hardly sweep in the early game). More than a late game sweep, i used chomp to reveal the opponent steels and to turn the tides of the battle in the early game, putting the opponent on the defensive play.
BTW, i don't see why Outrage mence is being so overhyped. It's not like he can kill his counters with outrage (ok, now he can OHKO starmie).
tl ;dr version: nothing can replace chomp.
Now, into the metagame changes:
CM jirachi is getting really dangerous, sweeping some teams without the fear of a Stabed EQ.
Gengar now don't need to carry HP ice, and with that free moveslot, he is free to use some other move (taunt, destiny bond, substitute, or even hp fire).
Lucario imo is the new top threat (no, not the new chomp).
Heatran is even better now. Not exactly because the chompless game, but because the rise of some mons (Lucario, Jirachi...) that is caused by chomp's absence. Scarftran is a top revenge killer and a resource for many resistences, and imo he is almost a must on any offensive team.
Now, into a mon that i love to use in the chompless metagame:
SDEF oriented Rhyperior: He counter Jirachi (without grass knot, of course), heatran (he can even take some earth powers), DD TTar (switches in a DD/Stone Edge and OHKO him with EQ), DD mence (Read TTar, except the Stone egde part, and replace the EQ OHKO with a Stone Edge OHKO).
With Megahorn/Stone Edge/Earthquake/Swords Dance, he causes a lot of problems.
Why Swords Dance? Because without that he can't really hurt any bulkymon. Skarmory is 2HKOed by a SD stone edge, and is forced to whirlwind you (roost? yea, EQ will really hurt you if you mispredict), Cresselia is easily 2HKOed and can't really hurt you (grass knot can, but hey, who uses that besides me?). Blissey can stall you if you lacks swords dance and so on.
Oh, and fun-fact: Rhyperior survives a CELEBI GRASS KNOT 100% of the time and OHKO him with megahorn (not that i'm going to let rhyperior take that grass knot, that just shows how Bulky Rhyperior is).
And like every other thing that i post, srry for poor grammar and things like that :p
EDIT: Syberia, this depends on that ability chomp would have if it did not have sand veil. Imagine it with, huh, intimidate?