Lucario has a VERY easy time setting up because he can force a lot of things out. Also, if something is switching into Lucario it's taking two attacks, the eqiuivalent of one +2 attack. Basically, a counter has to switch into all of Lucario's moves, so either Lucario boosts or gets an extra attack for free on the switch. If you have to predict Lucario's move to switch something in, then it's not a counter.
On the comparison to Mega Charizards - nobody is screaming for their respective heads on spikes, but I can imagine a reasonable argument for them being broken. Anyway, as soon as you know Zard's mega evolution you know its counters, while Lucario can run such a variety of moves on each set that you don't know what to counter it with until you know at least two or three of its moves.
On the thing about how easy it is to remove stealth rock - it's just as easy to set it up again, something you can bet a Lucario user will be taking the time to do if you have a Moltres or Zapdos or Gyarados.
Finally, usage has no relation to brokenness whatsoever. If something is broken, we ban it, regardless of how many people are using it.
How does Lucario have an "easy time setting up?" What can he force out? Also, a common mistake made is to let Lucario force something out if you indeed have something that can be OHKOed by +0 Lucario out. It's better to sacrifice something to cripple it. If it uses SD, you can kill it with Excadrill or Tyranitar or paralyze it or something. Let's see what Lucario can set up on from the top 50:
Rotom-W: no, Will-O-Wisp
Aegislash: no, Sacred Sword
Talonflame: no, Brave Bird or Flare Blitz or Will-O-Wisp
Genesect: no (only when stuck to Ice Beam, which is rare)
Greninja: no, Hydro Pump
Charizard: no, fire moves
Lucario: no, fighting moves
Heatran: no, fire moves
Gliscor: no.
Garchomp: no, Earthquake
Azumarill: no, Play Rough or Waterfall or Superpower
Scizor: yes
Ferrothorn: yes
Tyranitar: depends. Can be forced out but you can also kill Lucario if he chooses to set up while you use EQ or Superpower.
Conkeldurr: no
Excadrill: depends, for some reason as TTar.
Dragonite: depends. It depends on Dragonite having Multiscale on and Lucario having Ice Punch. You can also keep Dragonite on Lucario in case it uses SD.
Venusaur: no. He's a good Lucario counter with Sleep Powder.
Mandibuzz: no, uses Whirlwind.
Gengar: no. Outspeeds Lucario on turn 1.
Espeon: no. Outspeeds Lucario after mega evolving on turn 1, crippling him.
Mamoswine: depends.
Goodra: no, can take a hit and OHKO Lucario.
Alakazam: no.
Landorus-T: can take an Ice Punch and kill Lucario.
Togekiss: no, paralyzed.
Skarmory: no, Whirlwind.
Breloom: no, Mach Punch.
Infernape: no, outspeeds Lucario on turn 1.
Volcarona: no.
Gyarados: no. Good Lucario counter.
Latios: no, outspeeds on turn 1.
Mawile: no. owned by Play Rough.
Trevenant: no. Will-O-Wisp.
Cloyster: eh, depends on Shell Smash being used.
Pinsir: no.
Blissey: yes.
Sableye: no, Will-O-Wisp.
Smeargle: depends I guess? He's not really something you set up on because he has a Sash and Spore. He cripples Lucario if Sticky Web is up.
Sylveon: yes.
Klefki: no, Thunder Wave.
Clefable: no, Fire Blast.
Donphan: no, has Sturdy and Earthquake and is a tank.
Galvantula: no, same situation as Smeargle but he has some strong attacks.
Starmie: no, is always faster than Lucario.
Tentacruel: depends on luck. Tentacruel can tank a hit from any +2 move Lucario has to offer, so he can use 2 Scalds, crippling Lucario a lot with a good chance to burn.
Forretress: yes.
Bisharp: depends on whether Bisharp is +2 when Lucario comes in.
Salamence: no.
Thundurus: no.
We have 5 yeses and and 8 "depends" out of 50 pokemon.
An important lesson to learn here is that Lucario setting up is not easy on a lot of these "depends" Pokemon because it depends on correct prediction and luck. Will Lucario use SD or CC on my Tyranitar? You can't always be successful. You guys are vastly exaggerating this whole issue.
Dude, you can't argue for Mega Charizard's set being unknown and then say it's different from Lucario. All you need is a turn to see Charizard mega evolve. Similarly all you need to do to see which set Mega Lucario has is to see him set up or use Aura Sphere or Close Combat or whatever. That's it.
Usage has everything to do with brokenness. You can't know what is broken and what isn't without usage data. You need practical experience to conclude if something is broken; maybe not in cases like Arceus, but certainly so in cases like Mega Lucario.