They should happen during the game.
Perhaps you could do something like using levels or perhaps something more advanced.
"Energy". Energy is earned by staying alive during battle (more on harder difficulties) and upon dying you lose all the acquired energy for that round? Some "weaker" pokemons could then be balanced by having access to evolution trees quicker by using less energy?