Stone Rush is interesting: it does 35 base damage to the opponent, and 15 to you. So on balance, you come out ahead by 20 damage, which is equivalent to a basic attack like Punch/Bite. However, you are significantly speeding up the game, which makes going first much more valuable--and he has a built-in spammable 25% speed debuff, so against many pets you'll get to go first despite having 228 base speed.
Stone Rush is also great because you only take the blowback damage if you hit the opponent, so it's relatively risk-free. The 1 round cooldown is slightly annoying though--but in this case you'll almost certainly take Sand Bolt in slot 1 so it's less of an issue.
As for Sandstorm+Stone Rush: normally Stone Rush is 35 for them and 15 for you; under Sandstorm, it's 30 for them and 10 for you. So it's still a difference of 20 damage, which seems like a wash. However if you look at a basic attack like Punch: it's normally 20 damage, and 15 under Sandstorm. So, although you're reducing overall damage and thus reducing the value of a turn (and thus reducing the value of Sand Bolt), you're now breaking the symmetry of Sandstorm and coming out ahead on damage. On balance, I suspect it's worth it.
The breed 7 Sandling has 1709 health, 289 power, 228 speed -- it outspeeds a 304 speed opponent with the Sand Bolt debuff, and Stone Rush hits for 464 under Sandstorm (plus 155 damage to self). This is pretty good! I'm assuming that the Elemental passive will prevent the -10% hit debuff from applying to the Sandling, but will not allow the Sandling to bypass the opponent's Sandstorm shield. But if it does... ouch.