I'd figured out the technical aspect before worrying about the story first. There are over 600 pokemon, and each of them will have a variety of different stats. Implementing that alone (not even worrying about the combat and other trainers) will be a challange.
Well, good luck. If you need help I really would encourage you to ask others, as this sounds like a massive project.