Yeah, you have to be kidding there. Megahorn at lv. 46 is very timely, and this is probably the only game when Heracross learns this move in time for the important battles (which is just about all the elites and probably the last gym or two). Besides the 4x weakness to flying, it's hard to understand what your problem with Heracross is.
Also, with the Dowsing Machine, getting a Fire Stone in Desert Resort is a matter of seconds, not an issue at all.
Honestly, I'd rather put up with twenty or so levels of Growlithe in order to get both Flamethrower and Crunch and evolve it into Arcanine rather than evolve it straight away and get...Extremespeed. Not to mention you can Relearn Extremespeed after you evolve it. It's perfectly reasonable to have E-Speed, Flamethrower, Thunder Fang, and Crunch as your endgame movepool.
Though, that's just me. Growlithe has fine stats for waiting twenty levels, though Flare Blitz I'd rather not use, simply because Flamethrower is good enough for Arcanine, and the recoil isn't worth the boost in power for it. Outrage isn't all that impressive, either.
Sandshrew - Mid Tier
-Availability : Desert Resort. It'll probably be the first thing you find. It's that freaking common.
-Stats : 100 Attack and 110 Defense is great, but...that's kind of the extent of the good things. 45 Special Attack and Special Defense means it can't take ANY hit from a Special Attacker without taking a boatload of damage, and with 75 Base HP, it's probably going to be in trouble . Sandslash is also pretty slow, having a 65 Base Speed stat.
-Movepool: Simply atrocious. Most of the game you'll be using Magnitude, Rock Tomb, Shadow Claw and Swords Dance as your four moves simply because it doesn't get ANYTHING else worthwhile. Sure, you could slap Aerial Ace on it, but most Grass types will outspeed you anyway, so what's the point? Putting salt in the wound of having to deal with Magnitude for thirty levels is that it can get Earth Power by Move Tutor. Yes, Base 45 Special Attack sure makes that worthwhile, doesn't it? It does get Crush Claw, I guess...and Dig, though I'd rather be dealing with Magnitude than use Dig. On a positive note, you can give it Rock Slide.
-Major Battles: Sandshrew would have been nice for Roxie...but you can't get it until AFTER Roxie. You can use Sandshrew to counter Dwebble in Burgh's gym, I guess. It does great in Elesa's gym, due to the gym now only having ONE Emolga rather than Emolga up the wazoo. Clay's Excadrill poses no problems for Sandslash, and it can do reasonably well against Skyla using Rock Slide. Sandshrew really doesn't have the defense to deal with anything in Drayden's gym, and it REALLY doesn't like Marlon's gym. It does perform well against Colress and his Steel type team, though. E4's kind of a crapshoot for Sandslash. It can get Shadow Claw, but the things it could use Shadow Claw on are not only faster, but use Special Attacks. It can kill Grimsley's Bisharp, but what Ground type can't? Of course, Swords Dance is nice if you can get a good one in. Just stay far, far away from Caitlin and Shauntel.
-Additional Comments: With Sandshrew, it's just been a long, hard journey. It hasn't really shone in any of the Generations it was in, and although getting Magnitude was nice, I had to put up with it for thirty levels before it got Earthquake. In this generation, Sandslash is completely outclassed by Excadrill, who is bulkier and has a movepool, and by Krookidile, who has two great abilities and a decent movepool (and fake bulk if you have Intimidate). It simply isn't worth the effort to bring Sandslash to the top, as it's probably the worst of the Ground types (unless you count Stunfisk? Nah, it's Post-game). It has a mediocre movepool and stats that are frankly outclassed by its bros Excadrill and Krookidile.