I know how you feel - if at all possible I want to catch rares instead of upgrading them. I can confirm that Erudite Manafiends do come in rare naturally, as I caught mine rare after deciding I too didn't want to bother stoning one. However due to the slower respawn it does feel like a bit of a struggle. I'd suggest physically killing off any poorer qualitymanafiends you come across*, to force a fast respawn. The area seems to be flagged to keep a certain number of battle pet versions of manafiends at all time, so one of the critter ones will take the place of those that you kill off.
* (I only use this method if there's not other people pet battling in an area. I also avoid killing anything that has a rare secondary pet, as a courtesy.)