Hi,
I'm just setting up a shop and dealing with the same issue.
The best way seems to be to do it using zip/postcodes in the tax rules, assuming the Canary Islands, Ceuta and Melilla each have unique postcodes.
In Germany there are two areas with 0% VAT, Buesingen and Heligoland, with Postcodes 27498 and 78266 respectively.
So I had to set up the following tax rules for germany:
Postcode range 00000-27497 has 20% VAT (or whatever the normal rate is for you)
27498 has 0% VAT
27499-78265 has 20%
78266 has 0%
and 78267 - 99999 has 20%
Thankfully there are only a few regions like this that aren't set up as countries in Prestashop! The others, FYI, are Mt Athos in Greece, and in Italy Livigno, Campione d'Italia and Lake Lugano
Before doing it this way, I tried using States and setting up each of these regions as a state. This also works, but is clumsier: you also have to set up a state for "Rest of Germany" that the majority of customers not in any of these small areas has to select, and it is confusing to them as they are not actually states, plus you have to make up a false ISO code as they don't have official ISO codes. But I haven't checked whether the areas in Greece, Italy and Spain have unique postcodes - if not, I'll have to use the states approach.
Tim