An NPC you can speak to named Mr. Focus (or similar), who can teach your pokemon to 'focus' their training on certain stats - meaning that they only receive EVs when they defeat a Pokemon that yields that kind.
Easy EV training that can be integrated into the main playthrough. Make the game's trainers have good EVs too, to compensate for the increase in power you now have.