I'm going to say yes, you'd need a new cert. Other state's road worthy certificates (or wahtever they are called in other states) don't apply in Vic. I'd assume the eng cert is the same.
You'll definately need one for the 20v. I noticed a while ago there was somebody on here i think selling a 16v 4age equipped ae86 and included in the sale spiel that no eng cert was required due to some reasons (i can't remember what they were). Anyway, whatever those reasons, that car needed a cert too.
Any engine that is not standard in that vehicle in Australia requires a cert in Victoria.