Hi Paul,
As said above, unless you have the appropriate visa the only countries you can legally work and live in is Australia and New Zealand. Which of course narrows the international airlines down to Qantas, Australian, Air New Zealand (must be living in NZ at time of application) and Pacific Blue.
As you probably already know, Emirates, Gulf and Qatar also accept foreign nationals. I think also some corporate jet companies in the middle east also allow foreign nationals.
Hope that helps!
SG
