Games usually make it to New Zealand within a couple of days, and Australia will sometimes get them about a week after we do. With such a massive title, though, I expect we will get it the same day as the USA, just like with Doom 3.
I'm afraid Valve won't be releasing the game to any countries in the southern hemisphere, either via retail or Steam. Something about the Source engine being unstable when being played upside down apparently.