Ancestry has death records for Melbourne (which is in the state of Victoria) to 1985 and marriage records to 1920.
Ancestry also has various immigration records to Melbourne (Victoria)

Victoria also has it's own site PROV (just google) with immigration indexes, wills etc for varying years (could prove useful)

VIC BDM (just google) is online if you need to order death certificate (once you find his death) etc to verify wife/children..
Certs cost $20 and can be downloaded/printed instantly.

Let us know if you get stuck.

Kellie