The barbarians come, and the player with the least amount of active knights has a city and 5 settlements on the board.
The city would normally get knocked down to a settlement, but all of his settlements are already on the board.
You turn your city marker, and treat it as if it were a settlement. From the Catan FAQ:
FAQ - Frequently Asked Questions Barbarians III: Players are Defeated - What happens if I have to downgrade a city to a settlement but don’t have another settlement in stock?
Answer Turn one of your cities on its side and treat it as a settlement until you have upgraded it to a city again.
In the games we play I turn the city upside down (to act as a marker for a town) and declare the village supply to be at
-1. The player will need to build at least two cities before (s)he can build another new village.
I tried finding an official ruling, but it does not seem to be mentioned in a manual.
Page 11 only has this, which completely ignores this not-quite-so-rare situation.
[Edit] The computer game Catan: Cities and knight from Catan GmbH seems to agree with this.