The way I beat that mission was to first build bridges keeping the enemy from building bridges to my island. Completely surrounding his island with your bridges would be best. Then you'll be safe to build cannons that will attack his workshop from a safe distance to avoid disk throwers. He may keep rebuilding the workshop, but that only means more storm power to you every time you destroy it. Then, when he can no longer build any disk throwers you attack his temple and capture his priest. Simple.
Don't mind harvesting for storm power. If you do it right, you won't need to. =P