Hi,
The solution is indeed to create a "rest of the world" shipping zone with all the other countries as sub zones and then link that zone in your shipping method.
Creating a "rest of the world" zone should only take a minute:
You go in System>Zones
Click on "new"
Enter a name for your zone, select the type "shipping zone" and save once.
Click on the "add" button of the "sub zones" area of the zone which opens a popup to select the zones to add.
Change the "All zones" dropdown to "countries"
Change the "Display" dropdown of the pagination at the bottom of the popup to "all"
Then, click on the first checkbox of the listing and click on the "OK" button and that will add all the countries to your zone.
Then, you can simply remove the countries you don't want from the sub zones listing and save your new zone.