There aren't any strategies that have you sitting on significant unhappiness throughout the game - it is a serious detriment to your empire.
Conquest can produce some significant unhappiness. In my experience, it is almost always worse in the long run to annex a city. The happiness hit is overwhelmingly strong when you annex, and it's significantly less strong when you puppet. Puppeted cities will eventually build happiness buildings, although it can take a while.
Once you get past the "middle of the road" difficulty levels, happiness is kind of a key bellwether when it comes to expansion. I tend to only build a new city when I can take a happiness hit, and if I can gain access to at least one but preferably two new luxury resources. Strategic resources might trump this, in certain cases. It's very difficult to survive without Coal for Factories, for instance.
Razing a city can be a very legitimate strategy. If you conquer an enemy, and they have some tiny cities that are not near luxury/strategic resources, burn 'em to the ground. Expansion is the primary way you're going to get more powerful, and expansion is heavily limited by happiness. Hanging on to cities that aren't helping you become more powerful is a waste.
Unhappiness is a factor of both the number of cities and the population, so if you've gotten to a balancing point, you might consider setting your cities to "avoid growth" - this will up their production and down their food intake, in an attempt to keep them from getting bigger and producing more unhappiness.
Since happiness is generated by buildings you unlock through technology, science is an important key in maintaining your happiness balance. With Patronage, I'd expect you to be gifting/bribing city states to get access to their luxuries. You can also trade excess luxuries to other civs, if they've got something you need.
Best Answer
In Gods and Kings, Militaristic City-States can sometimes grant the Unique Units of civilizations that are not in the current game as their unit gifts. Each Militaristic City-State grants a different UU, which can be found from that City-State's interaction screen.
Likely, the AI Civ in question made friends/allies with a nearby Militaristic CS, which is now granting them Cho-Ko-Nu.