I have a few ideas.
1] Pokemon with the free roaming, free range questing of Skyrim? Pretty much, you have a basic start to give you an idea of the controls and what to do, then once you complete that section, you are free to go where you place and the game dynamic levels opponents based on how long you've come [EX: Your highest pokemon level is 50, opponents will have pokemon between 45-55 ranges and so on.].
2] I can see a Pokemon x Street Fighter with SF mechanics. Heck, I play MUGEN a lot and I have Lucario, Mewtwo, etc playable. So it works.
3] For some reason, I can also see a Pokemon x Fire Emblem mix as well. Similar to the Dungeon series, where there are no humans, but you play as Pokemon in teams and such. Giving you freedom to replay areas and such, but still having a straight-forward story.