You don't say whether you are using professionals to design and plant the garden; if you are, they usually clear the area prior to doing the work anyway. However, if you are wanting to do all that yourself, the usual advice when taking over a new property is to wait a year before radically clearing the gardens, although anything large or out of control you know you won't want can be reduced or removed. There are a couple of reasons for this: 1. to see what comes up - some plants will be below the soil and may not appear until the right time of year (bulbs for instance) and there may be some you'd like to retain, even if you move them elsewhere; 2. it gives you time while actually living in the property to work out how the light falls, where the sun reaches and where it doesn't, what kind of view you'd like through different windows, which areas remain damp or get waterlogged or very dry, and so on.
If you want to clear it immediately, I'd suggest you call a company to do it - in the UK, tree surgeons usually have a team that will come in and do this work, including boring out tree/shrub stumps and major roots down to a certain depth, usually around 18 inches deep. Bamboo is difficult to eradicate, so the area where that grows needs to be dug over well and any root material completely removed. Whether a contractor's team will do that efficiently I'm not too sure - in my experience, bamboo is persistent and may reappear in other places nearby, and some bits of root are inevitably missed during a single operation, so vigilance and remedial action is usually required for the next couple of years.
If you decide to try to do it all yourself, you will likely need a chainsaw to cut down large woody plants and trees; take advice about how to use one safely, or find someone who is skilled in using one, particularly when it comes to cutting down trees. It's always better to bore out trunks and large roots after cutting down, and you should be able to hire a borer for that purpose, though they're not particularly easy to use. In regard to whether you choose to use machinery (cultivator, rotavator) to turn the soil over/dig, it depends what is growing - some plants (especially weeds) regenerate from tiny bits of root material, and machinery tends to chop up roots and spread them far and wide, meaning lots more of the offending plant the following year. If you dig by hand using a garden fork, remove all root material as you go.
In terms of the soil, you don't need to replace it, in fact, retaining the top soil is very important, and in particular, any subsoil excavated for hard landscaping should not be placed elsewhere on the surface of the garden. Subsoil should remain below the topsoil level, because it's the topsoil that is the fertile layer (usually about a spade's depth deep). The only time soil should be removed is if it's contaminated, and since your soil is already growing plants, it clearly isn't. Soil amendment prior to planting though is another matter - for areas where you want to grow anything, adding as much humus rich material as possible to the soil is a good idea, so things like well composted manure, leaf mould, spent mushroom compost, in other words, any organic materials which have been composted. This will improve soil conditions and increase soil fertility. If the soil is very heavy clay, you may need to emend with horticultural grit as well as lots of organic materials.
Screening out dormant bulbs which are currently below surface level can be difficult to achieve; most bulbs produce offsets which are tiny, and it's very easy to miss those when attempting to clear a garden, even with screening/sieving the soil - another reason to wait and see what's growing where, because once they produce green growth above ground, you can more easily dig them out.
In terms of planting, the optimum time for most plants to go in is autumn, assuming it's cool and damp; where you are (assuming you mean Melbourne Australia) your spring must now be underway. Otherwise, planting can be done any time if the plants are container grown, but they must be kept well watered, especially during hot dry periods. Working the soil can be done at any time so long as it is not waterlogged nor frozen, although heavy clay soils can be difficult to cultivate if it is very dry.
In respect of chemicals, the use of those should be avoided where possible, though there may be a need for some judicious use of specific weedkillers where persistent regrowth is an ongoing problem.
