I'm wondering whether it's legal to sell this without certification
If you want to sell it within Australia, No (that was easy).
how to get it cheaply
I don't think it is possible to do it cheaply. The cheapest would be at a wild guess maybe $4000.
It would be classified as a declared article and as such needs safety testing.
It would also need EMI testing.
One testing place should be able to do both lots of tests.
First thing you need to do is work out what tests they do exactly and make sure it passes them all even before you even send samples to them.
It's called pre-compliance testing.