One of the best I found was Dunsparce, however, he is harder to find. You know those rustling grass spots where you'll find Audino most of the time? Yeah, you can find Dunsparce in one of those rustling pieces of grass in Floccesy Ranch and Route 20.
Here's a few more:
- Venipede: Rollout, should have upon capture in double grass on Route 20.
- Mareep: Power Gem at level 29. (Floccesy Ranch)
- Marill: Rollout at level 10 (this one is tricky, you have to evolve it with happiness before it hits level 10 somehow). (Evolve Azurill, found at Floccesy Ranch and Route 20)
These are your options, I believe. Without trading of course. I'd highly recommend trying to find a Venipede or Dunsparce for your rock type moves first, and then trying Mareep or Marill if they both fail.
Hope this helps and good luck! :)