People normally just let EVs and IVs build up naturally for pokemon they wanna use for the story. I mean, play the game without worrying about EVs/IVs at all. Play the game like you never knew about them
EV training is particularly meant for competitions. Even without, you'd still kick ass in story mode. If you wanna start playing competitively, breed a fresh egg and train post-game like Lari mentioned (where you wouldn't have to fight any trainers).
Now if you still truly want to EV train during the story (I do so when I play an all-bug team), then by all means, do it with wild pokemon. Stop your journey, EV train in one place, then proceed. You cant "choose" which trainers to fight, so the best way to avoid "messed up EVs" is to simply max it before fighting anything else. Personally, I don't bother maxing more than one stat. Usually, I just EV train for a single stat for story pokemon, then just let the rest come in naturally since it's a real pain in the butt.
Oh right, since Lari mentioned the EV-reducing berries... in gen 4, they act like an opposite equivalent of vitamins. If your pokemon's EV is more than 100, one of those berries will drop it to 100. For example...
Attack EV = 252 -> used Kelpsy Berry -> Attack EV = 100
Attack EV = 103 -> used Kelpsy Berry -> Attack EV = 100
In Gen V, they removed the "100 limit". However, they just reduce the EV by 10. So yeah, in Gen V you can completely reduce 255 EVs to 0. You'll need 26 berries for that tho XD
Pomeg Berry – Lowers a Pokémon's HP EV
Kelpsy Berry – Lowers a Pokémon's Attack EV
Qualot Berry – Lowers a Pokémon's Defense EV
Hondew Berry – Lowers a Pokémon's Special Attack EV
Grepa Berry – Lowers a Pokémon's Special Defense EV
Tamato Berry – Lowers a Pokémon's Speed EV
Lastly, if you really want to bother yourself with EVs early in the game, [Pokecheck] may help a lot. Upload your pokemon and check it's stats - you'll find how much it's current EVs are.
On a side note, I wouldn't suggest "downloading" pokemon from there. It's filled with, uh, "illegitimate" pokemon that would ban you from battling online.