How about if the barbarians could capture cities. Additionally, they could even establish some cities (i.e. have one AI barbarian player similar to the WWII scenario in Civ2). The barbarian cities would not cooperate with each other and would not research techs (basically they would have only the default techs, i.e. those owned by every nation). I realize that you could hinder the barbarians by keeping one civ around and making sure that it did not progress well, but if you are planning to do that, then why play the game at all?
Ok, now, for terrorist activity, the "Red Nation" (i.e. barbarians early on, whatever you wish after that), if it has cities, could pool the resources to cause havoc in the "Civilized" (i.e. player and AI) civs. You could, therefore have unrest (all units would be "Red Nation"), revolts, sabotage, etc. Unrest could be either within your borders (if a city goes into unrest) or at the outskirts (the same way that barbarians come about currently). This way, there should be no situations of MA going against barbarian warriors.
The "Red Nation" (I use this because in Civ2 the barbarians and other nasties were red) units would always be uncontrolled by any VP-earning Civ. The red units would have there own AI priorities (probably beat up on the nearest weak units or go damage infrastructure). If the red units had a city, they would also do their best to defend that city (more or less). Cities that are red-controlled would be unable to be absorbed by culture (since the "Red" guys will have no culture).
This would sort of combine the ideas floating around in these threads (i.e. you could still have civil wars, its just that the new "civ" will be red cities) and what seemed to work for most of us in Civ2.
On this note, however, I would not like to see random ships showing up in the ocean full of lots of "red" combat units. That always seemed like a cop-out to me. If the "red" units are going to be produced, at least have a real reason for their popping up! (i.e. civil unrest, opposing civ funds them, whatever).