Kind of same story here. I am doing a PhD and my wife is a software engineer. We are on student visa.
As I said finding a job will be bit hard because of the visa type. Same happened to my wife. She went through to the final interview several occasions but got rejected once they asked for the visa. They are very reluctant to hire people with student visa. In some situations you may have to convince them that your wife is doing a PhD and therefore as the partner you can work unlimited hours. General perception specially among the recruitment agents is that partners of students can only work limited number of hours per week.
You may be able to manage the expenses until you find a job since your wife is getting a scholarship.
Securing the first job in Australia can be very hard because they always prefer people with local(Ausi) experience. So when you are applying for jobs don't limit your self to Melbourne, Apply to all the jobs available throughout Australia. Once you get your first job somewhere, work for some time there and use that experience to get a better job in Melbourne or any other place you like.