Well, luckily the exact example of 'Wally' can be rebattled during every trainer reset (Once every six hours IIRC).
As for the other rivals, I'm afraid there currently is no way to rebattle those aside from Blue at the pokemon league in Kanto.
I was training a Meowth to 100 but around level 70 my internet gave up during one of the horde encounters. When I logged back in my Meowth was evolved to a Persian, essentially erasing my work on it.
Change it so evolution prompts wont activate while a player is disconnected.