First I would suggest training special defense a lot because Rhyhorn is very susceptible to Surf and other special moves. His defense is already very high
You can check our various questions for locations in the games, eg for attack: http://pokemondb.net/pokebase/1425/where-can-i-ev-train-my-pokemon-for-attack
Unfortunately EV training can be pretty slow. You can't really get round the time it takes for each battle apart from turning off move animations. But you can reduce the number of battles you need:
- Use vitamins (they only work for the first 100 EVs).
- Pokerus doubles all your EVs
- Holding the Macho Brace doubles EVs, or you can hold the power items to gain an extra 4 EVs. See http://pokemondb.net/ev for examples.
If you don't have any of those items, you can use Exp. Share. Send out your strong pokemon and KO them. Your Rhyhorn will get the EVs from the enemy without battling. But this is slower because Pokerus doesn't count and you can't hold the other items obviously.