I think it would be cool if you added Npc Trainers as well. So it would be like the original games where you can battle a trainer and earn coins as well. However, if it's possible try to make it so the player can only fight the Npc once a day or once a week and every time they fight the Npc, the level of their Pokemon increases. It could also be possible to make the level of the Npc's Pokemon be based on the level of the trainer.
Ya this would be really fun. Maybe there location changes every time you battle them. Also I was thinking that the Npc could be part of Team Blocket! An evil origination that is being... evil? They need a better story