Spoiler :
So I finally got my barbarian challenge. Note first that I overcrowded a Standard Map (Terra Incognita) with 38 City States, and the standard number of Civs all on the Old World. Even then the savages got to thrive with a few encampments, spawning like rabbits.
During the early game I had hoped to turn the odd Encampment and get a free Brute (who get an awesome bonus when attacking now!), but they kept a worthy challenge by always having a couple Warriors hanging around and constantly threatening my worker inside my dominion. Gladly I didn't lose any of my units (then neither did they get too experienced with Defense XP out), but even when I was fielding three armies I couldn't overrun those troglodytes.
Right after my first setback--losing a warrior--my breakthrough came with a Settler. I managed to use my remaining military to escort him over along the northern coast, and finally he got into the settling spot (and what a spot!) stacked with a bold warrior. But the barbarians had brought in an archer (while I was still building my first), and in a supporting fire flanking operation they broke my defending formation, capturing the settler!
Luckily, his own attacker was now too weakened to keep a tight hold on their newly acquired ransom, so my remaining warrior rescued the settling folks without a pinch. Passing the turn saw an insurmountable fear that they could try a desperate even odds attack at my last warrior, but by now they knew their place.
I settled Hamburg, a city born out of resistance against raging barbarians, and quickly bought lands of Marble and Sheep to keep the greedy Indians out, and the rest is history.
Mods used:
My own Savage Lands: Increased Barbarian Activity
rspeer's Terra Incognita mapscript
zappara's Historic City States
Solver's Hebrew Civilization
Dale's Hardwood strategic resource
p.s. Wish me luck on my 50% roll against the barbarian Encampment!