大工ならFacebookのNewZealand BuildersやBuilders and tradesmen などのグループに参加して自分を売り込むといろんな方からメッセージが来ます(スキャムもあるかも)
今はリセッション中なので仕事自体が少ないですが、レイバーもしくはハンマーハンドで始めて見習いになるのが妥当かと思います。

rataさん、回答ありがとうございます。
TrademeやSeekはすでに活用済みですが、空振り状態です…。
派遣会社を使う手があるんですね、初めて知りました！
ありがとうございます！

＞経験としては日本で7年道路工事や施工管理をしており、オーストラリア３年間大工、ファーム、配送業をやっていました。

→これらの経験を証明するものはありますか？
日本でしたら職歴証明書と呼ばれるもの、または雇用主からの推薦状（あなたとの関係やあなたの職歴について言及したもの）ですね。英文で書いてもらえればラッキーですが、そうでない場合には英訳したものが必要です。
オーストラリアの分も何か証明になるものがあるとよいかと思います。

私の娘たちのパートナーは二人ともbuilderです。一人は保険会社で、もう一人は造園会社で働いています。Builderにもいろいろありますので、もしよかったら直接メールください。

一般的な回答で申し訳ないのですが、英語圏でいろんな経験ありなので、求人広告に応募されてはいかがですか？TradeMeやSeekなどの求人サイトで、職種を絞り込んで検索。あとは各地にある派遣会社(job agency)に相談するなど。そういう会社の外壁に、vacancyが貼ってありますので、直接行ってお話を聞くと何か出てくるかもしれません。私は、未経験で、豪華船の掃除の仕事を紹介されました。見つかるといいですね！