Hi Airhostie,
I believe that if you want to fly for an Australian airline based in Australia then you would need permanent residency. I was looking at possibly flying but have 2yrs residency, so I have to wait if I still want to pursue that in the future.
There are of course options if you want to apply for ground based positions within hospitality if you want to live here. I can' t think of another airline other than what RaverFlaver has already suggested.
I can PM you if you need any more information.
Exmax