What I saw one solo-runner do during his Shedinja solo run of Emerald was use the Wynaut Egg you get from the told lady in Lavaridge Town. It only knows Charm, Encore and Splash when it hatches, so you can use it in their double battle without it having an impact. You could also use a low-level Magikarp.
The problem with a double battle is that they kinda defeat the purpose of a solo run. As a solution, I offered up a sacrificial lamb which would do no damage to any opposing Pokemon, the Wynaut I had hatched earlier in the game.
It does bend the rules of a solo-run, but seeing as it is necessary to complete the game, it's not that big of a deal.
