Krokorok. Evolve from Sandile @ level 29, learns Crunch at 28 and Dig @ 32.
You can get either Sandile or Krokorok in the Relic Castle. Krokorok comes at about level 29-30 on the Relic Passage floor, or Sandile at around 27-28 at the same place. There are lower level Sandile on the higher floors.
There's also Sandshrew, and while Sandslash has higher attack at base 100, Krokorok is only the second evolution and has a base 82 attack, so I think in the long run a Krookodile will serve you better, especially one with Moxie.
You can also get Rock Tomb as a TM early on to deal with Elesa's Emolgas, which you can also find in the Relic Castle.