Absolutely. You'd almost reach that power gain with ECU alone. With headers, some small cams (264's), and a tuneable ECU you will comfortably get 15-20kw extra at the wheels Provided your engine is fairly healthy, and you already have an exhaust.
I cannot comment on the melbourne part, hopefully someone else here knows of good workshops down that way.