Make 'em lose! >:D
My first thought is poisoning and other status ailments, if that's applicable. This may be too cheap for a fanfic, but in the game almost any pokemon can learn toxic. Aaaand I just broke every pokemon story ever written. :)
But seriously, statuses are a big way to overcome type disadvantage. And like psyanic said, the best option is often to make the setting of the battle factor in to it. Good luck with your story!