Would it be possible for a Barbarian encampment to, if left alive long enough, turn into a City State?

Maybe if they have kidnapped a settler, and get it back to their encampment and hold it there more than 5 turns, it'll turn into a CS.

Unfortunately, not easily. You see, the list of civilizations in the game is set when the game begins, and that includes city-states. So if you want the ability for new city-states to be created, you'd need to create several additional civs at the start of the game and then not use them.

A similar method has been proposed for "rebel" factions, where a civil war could result in multiple civs, so it's not impossible to do (except on the largest map sizes, where you run out of civs; the game can't handle more than 22 regular civs and 41 city-states). But it's not easy, and your particular idea would also have a bunch of balance issues; a city-state that wasn't founded in 4000 BC will be FAR behind the curve, and not pose any real challenge for a "real" civ to conquer.

Now, what you COULD do is just have a Barbarian city create itself. No need for additional factions. But this could easily get out of control if you're not careful.