Unfortunately you still need country first. But past that, the point stands well. You'll need to adjust the form based on the country, obviously.

For the US you can use zip-5 to prefill bunch of data and zip+4 practically fills it all out for a lot of addresses.

Each country has some particular nuance though, so it's only as simple as "zip first" or "postcode first" in some locations.