Rock Slide is substantially better, as Excadrill really can't afford to miss. Plus, over two turns, Rock Slide does more damage on average, when you account for the flinch chance and the fact that Excadrill/Sandslash should be outspeeding your opponent at all times:
Stone Edge average damage = 100*.80 = 80
Rock Slide average damage = 75*.90 + 75*.90*.3 = 87.75 (the .3 is the flinch chance, meaning you get a free turn to do extra damage)
As you can see, Rock Slide does more damage on average (and that's not even accounting for the possibility of multiple consecutive flinches), it hits once more reliably than Stone Edge does, and the flinch can really screw with your counters. I didn't even know that Excadrill couldn't learn Stone Edge until you posted it; I figured it could, but everyone used Rock Slide because it murders things at +2 anyways, it's a much safer option, and the flinch chance is so darn useful.