I have never previously thought of mence as uber. But now you mention it, he fills all the criteria. Not a solid counter, has amazing unpredictability. Two overpowered stab moves (dracco meteor + Outrag) combine this with one of the best attack stats and one of the best sp.atk stats in OU. Then add the fact that he has dragon dance, and amazing movepool.
Now although usage in uber is never a factor, salamence is actually used in uber with success due to the fact it works well with rayquaza.
Also stealth rock is not a counter argument, why? Because if SR keeps salamene out of Uber, then why HO OH still in uber. I know HO-OH stats are insain. But if you think about it, she has the same attack and sp.atk as salamence, and she has an even worse SR weakness. She is also slower than salamence, and does not have a decent set up move and is therfore more predictable. Mence is actually more offensive than HO-OH! and has less of an SR weakness, yet HO OH is uber because it's too offensive and overpowered in OU, while mence is OU cause he has an SR weakness. They contradict each other. Ho oh's main advanatage is amasing sp.def and that is it really, a better hp stat, but due to SR definately a worse typing.
Bassicaly Salamence is uber by all criteria. The last nail in the cofin for Garchomp was his ability sand veil. Well intimidate is arguably an even better ability.
Then we get onto how would it affect your team. I always carry 2 checks, for mence, one for the DD set and one for the mix set. DD mence is also the main reason people put a scarf on gengar, starmie, latias etc.
Scizor has risen high in useage, and this may be because he is a check to salamence along with his other useful roles. But I garuntee the metagame will completely change if mence goes to uber. If scizor went not much would change, because he does not centralise the metagame.
What is the point in uber, to make the game more balanced, more fun. I would definitely prefer it if mence was uber.
Then compair salamence to 3 solid OU's, Gyrados, kingdra and dragonite. In terms of sweeping they are very simular, but salamence outclasses all of them in terms of attacking stats, both speed and attack. Yet they are still used, because they are still good, is just Mence is Uber good. This leaves me to my last point, salamence won't be missed, because there are many OU's to fill his role.