We begin in the kingdom of Ignis. There, Hideyoshi is pondering a world filled with people that could communicate with Pokémon; not just Warriors, but all people. After being denied by Kanbei, he thinks of conquering all seventeen kingdoms to summon the legendary Pokémon...
Now, that is NOT a joke. You will effectively have to replay the whole game again and conquer all seventeen kingdoms. So, yeah, crap.
Now, the more painful thing is this. The other Warlords are more likely to invade other Warlords. For example, Valora is known be Steel-typed, correct? Well, after Nobunaga conquered it, we saw Scyther, Roggenrola, Cubchoo, and so on versus what was there earlier. ANY walkthrough ANYONE makes for this story is untrustworthy.
So you'll be forced to rely on your own smarts for this one. Early on, it can almost be guaranteed you'll fight the natural enemies. But, by the time you start hitting kingdoms eight and nine, you'll be likely fighting very different Pokémon than before.
Go by your own smarts, and learn to check each area each month for decent recruitment options. Good luck.
On a side note: We will let you know that, given your initial condition, your first best bets are Greenleaf, then Aurora, then Fontaine after recruiting some Grass Pokémon from Greenleaf.