When you begin with the Mongolians, barbarian villages will join you once you have defeated their village.
The easiest way to win with a certain country or person is to go into "Scenarios" and choose "Lightning Round". Set the difficulty to "Chieftain" and select the person you need to win it with. Then, just concentrate on upgrading Tech. You only need 24 Tech so it will be fast. Choose the Techs that take the least amount of time to research. Try to avoid wars with the other nations, but do not give Tech to someone if it will give them the lead. By doing this, it should not take very long to win.