Not private messaging, but the ability to leave a message/mail on someone's village
I remembered just now a game I used to play called Farmville, long ago. Any way.. there was a feature in the game that allowed you to visit a friend's farm and plant a little mailbox in which you can write them a message.
Private messaging in CoC wouldn't be convenient, so this seems like a better more reasonable idea. I also realize that this wouldn't be convenient to top world players or members of top clans because their base can be visited by anyone..
So, you can either make it optional whether or not you want to receive messages OR only be able to receive messages by people on your Game Center (or Google+). The method does not, of course, have to be exactly how I explained, but anything similar would be a fun and good addition to the game.
The messages should be censored just as they are in global chat only if messages can be sent by anyone. However, if messages are only sent by Game Center friends then i doubt there is a reason to censor your friends' messages.