The idea sounds fun, but don't you guys start to think it would be too much work to deal with an over-powered barbarian unit? Besides, terrorists aren't barbarians. They are agents of various organizations that are often funded and trained by a country. I think a better representation would be a combination of the privateer/Knights Templar concepts.
A civilization would be able to build a small wonder in the Industrial/Modern Age which would allow them to train an anonymous unit called a Terrorist or Fundamentalist which would have a hidden nationality. However, whenever this unit is used, there is a chance (let's say 25%) that the unit's nationality will be exposed.
Another idea is that it would be an invisible unit (like the assassin), but instead of having an ADM rating, it would be counted as an artillery unit with lethal bombard. Whenever the unit enters another nation, there's a chance the defender will expose the unit. The chance increases every turn the Terrorist spends in another country.
Both units would cause a reputation hit and a declaration of war if uncovered, and the defender would have a better chance of defense if they had an Intelligence Agency.