When we arrived 1 year ago we didn't have jobs either. The best advice I can give new migrants is to search for a private lease in terms of avoiding real estate agents. We rented privately, advertised in the Advertiser and it worked for us! Before that we had some open inspections near Glenelg and Westwood, either too many interested people or rubbish places. Real estate agents are a good option when you really want to live in that unit/house and nothing similar is advertised in the papers.
We had our bank statements ready to show that we could afford renting our place because we had no job. Our search took us 3 weeks before moving in (1st week we didn't seek permanent accommodation because of job interviews). After 4 weeks hubby could secure a job.
Sallyh's advice is really good, too.