In Victoria, since 2014 in order to replace or construct a boundary fence, under the Fencing Act you need to have a valid fencing notice. If both parties agree to the works then a contract outside the fencing act can come into existence, but you would not be able to seek mediation from the Magistrates court should something go wrong.
Even if they choose to pay for building the fence themselves, under the Fencing Act they cannot enter your property without a valid fencing notice. If there is a fence or established boundary you can ask them to leave as they are trespassing. If they are building on the boundary and therefore they remove the fence, under that Planning and Environment Act there is no provision for them to hop on your side put all their bricks and mortar and scaffolding on your property. They should do that all from their side.
If they show hostile intent then you are well within your rights to ask them to leave, and immediately inform them that they are no longer welcome on your property.