How about giving Pokemon two movesets? Like the 2nd moveset will stricly be moves useable outside of battle but a Pokemon can only use its 1st moveset in battle.
The number of moves in the 2nd moveset will depend on the Pokemon. (like Bidoof can have 4 while a Legendary has 1)
Think its a good solution?
Proud Member of the Mega Mario Movement Yummy Yoshi Yankees