Hi,
getting the Certificate of Validation is quite straight forward and can be done completely in advance from home.
The thing, that really can be a showstopper is the ASIC, as at will take another nearly 2 weeks from your arrival until you have it in your hands. (not to mention all the red tape before)
However the ASIC is not required at every airport, only where there is regular public transport.
If you only want to do some shorter trips from bigger cities with pure GA-airports (e.g. Sydney/Bankstown over the harbour, into the blue mountains, along the coast to Brisbane/Archerfield, from Melbourne towards the twelve apostels, ...), you can get away without ASIC.
With some planning also amazing trips are already possible without ASIC (e.g. via Renmark to the Flinders Range).
However, once you come to the real outback, there are only few airports and where you can get fuel, most likely there is also RPT...
I did the complete exercise last year, if you need more info, I am happy to answer here or via PN.
Regards,
Florian