Need help with Link a Device

Hi!

I have been playing Clash for over a year and I have a level 124 base. I started playing on an iPhone 4S. Then I got an Android Tablet. I linked my village using the link a device as would be expected. Soon after, I replaced my Android tablet with a new one. My village was synced with Google+, but during that time I had to delete my Google account due to constant spam. Now I am about to replace my iPhone and as I attempted to link the village, yet again with a new Google+, it says village already linked. This is an urgent situation and I have gotten so far in the game to lose my village, to lose it. What is the solution?