Let's take a look at his Pokemon:
Sandslash, Krokorok, Excadrill
Notice what they are all weak to? If you chose Water, you are correct! Catching a strong Water type or using a Water move is a good move against Clay. An example is Azumarill with Huge Power.
Spamming your Grass type moves also work. A good Fighting or Fire type on Excedrill takes it down pretty quickly.
If you tell me your current team and their Levels, I could help a bit more.
Azumarill should have learned Aqua Tail by now. Use that against Clay. Does your Azumarill have Huge Power? Pignite's Arm Thrust or any of its Fire moves will dent Excadrill.
Also, I highly recommend you Level all your Pokemon up to around Level 30.