I believe you're in the right, but make sure you follow the correct process. The first step would be to serve a notice for breach of duty on the landlord, if you haven't done so already. If you're in Victoria, there's more here: http://www.consumer.vic.gov.au/housing-and-accommodation/renting/during-a-lease-or-residency/breach-of-rental-responsibilitiesThat's what I'm thinking. At the moment, I'm the one at a loss at someone else's fault. On top of that the landlord expects me to cover his 'Try' to provide me with Internet connection which was part of the agreement anyway. And find him a new tenant as if I'm the one who expressed the desire to break the contract.
It seems ridiculous to me, but I new to the country and still not sure if common sense can be applied here.
If you leave as a result of the landlord's breach, obviously you have no obligation to find a new tenant. But make sure you've given the landlord the opportunity to remedy in accordance with the notice etc., or it may be seen as a voluntary breaking of the lease on your part. (Unlikely if you have email trail or other documentation substantiating the length of time the landlord's been in breach, but just in case.)