Up front, I'm not a parent, so take my parenting advice with a good handful of salt.
I'm a software developer, I've worked on games very much like Clash of Clans for a number of years and can safely say I'm an authority on the psychology and mechanics of them.
As a child of around your sons age I also had to deal with my parents making efforts to minimise my game-time, so perhaps I can offer some perspective on your son's mindset in this too.
Right off the bat, I think you've done the right thing with the Total-Kill approach (uninstalling and blocking on the phone) Your son has broken your trust by lying about his activities and there should definitely be consequences.
That said, He will undoubtedly be very upset about this (you've probably already had to deal with sulking or tantrums about it by now) and will be trying to find any means to circumvent you.
As a child, my parents set hard limits on my computer time, two hours a day as a maximum. I of course found this intolerable and since the computer was in my room and my parents frequently busy with other things I found it easy to get away with it. Eventually my dad wrote a program to shut down and block access to apps that weren't on a specific list after a certain amount of time each day.
Automation in parenting!
And it worked very very well for about..three weeks. I took the installation of PartyPooper.exe as a declaration of war, went through the files, studied them in depth and learned hexadecimal to rewrite the time-limits. Dad figured it out a week or two later and gave up on that approach. He was simultaneously frustrated and proud of me :P
You may find that there are parenting apps out there which allow you to lock down the phone, or time-restrict access in a similar fashion, they're likely to be more secure than dad's 20 minute script.
Clash of Clans and its ilk are explicitly designed (seriously, it's in the technical documentation) to have a session-time of about 10 minutes, with repeat visits every few hours.
If you set up a parental-control app to permit access at two or three set times for about half an hour at a time at most, he should have all the time he needs to play the game and keep things moving, without it dominating his every waking hour.
I would also make sure that if he wants to buy things on the app, he has to come through you. it's his money, but you need to be in the loop if it's via your card.
What you need isn't to fully and wholly block access, it's to force a measure of control on him. He needs to have other things in his life that occupy his interest. He needs to be able to switch off from this obsession.
As long as he can do that, he reaps the benefits of an active social life and good times with friends.