- I'm guessing they're hitting with Shadow Sneak? If so, use a Normal type. If it's Sucker Punch, I don't really have any idea other than to switch off your battle animations (if you haven't been doing so already). There's not really any way of not making them hit with Sucker Punch.
- if it's really a problem, get something with No Guard. Machamp and Golurk both have Earthquake and the ability, so they can hit Sandshrew no matter what. If you have more of a problem with being buffeted by the sand, then use something that's part ground (Swampert comes to mind).
I would also say that EV training is something you do in the background, like when watching TV or reading a magazine etc.; that helps to make the training go faster, so you don't just sit there staring at your Greninja knock out Sandshrews for an eternity.