Hi Mate
Depends on your Skills - Trade what you want to work as if you want to earn good money or just cover yourself - I take it you are not a diving Instructor ??
But there are lots places in The world however getting a work visa is alway the hardest Part .
I can recommend the Maldives , lots Jobs there in Lots fields and anywhere you would work you could dive on Days off and staff usually get a really good discount .
The Caribbean is also really nice and Lots places can dive off the beach , get a job in a Bar or somewhere , Utila/Roatan in Honduras , Curacao or Bonaire are great places to hang for 6 months .. there are 1000's Places - I see you are In Australia so Guess Not so many Languages you speak as That also Helps , nearer Home - Fiji, Vanuatu, Indonesia, etc But would be better find a Job first ..
I have spent 20 years Living and working everywhere - mainly as a Diving Instructor but met many other foreign staff working in various Jobs in the same places ..