Some of the assumptions you make above are not actually correct, although they're close. Let's start with Land Rights.
In Australia, all freehold land is 'subject to the rights and liens of the Crown', meaning that YES, the government can resume that land and pay fair compensation for it to the current owners.
The problem is leasehold, and that is only a problem because of the famous Mabo case back in 1982. Ultimately, Australia was colonised by Britian under the legal concept of Terra Nullius, or Empty Land. Under that concept, the Crown owns it all, but can sell or give that land away if it wishes. In many cases, grazing and farm land was 'leased' out instead of given or sold. So, the Eddie Mabo case basically says that Terra Nullius is invalid because Aboriginal people were present in Australia; therefore, where the status of the land hasn't been explicitly been changed through granting of title or exercise of sovereignty since, the land is covered by the concept of Native Title.
In practice, that means that land which is not 'owned' by either crown or private individual is ultimately owned by the Aboriginal people. This initially created a massive issue for generational farmers on Pastoral Leases, but this is not so much a problem now; at least it's not in the news anymore so I'm assuming this is largely resolved somehow.
The point being that people on Pastoral Leases actually CAN'T have their land resumed by the Crown; the land has to be dealt with through the Aboriginal caretakers.
This is where things start to get interesting for this solution; land isn't privately owned in the Aboriginal culture. All property is essentially tribal. In point of fact, from an economic perspective this is a very communistic structure but it works very effectively because it's not about money, it's about effort. Everyone contributes to the tribe through their time and energy and they deeply feel their connection to the land as custodians of it rather than owners.
So; sure, you can build a canal through it to bring water to the desert so to speak, but the custodians of the land won't have economic considerations about this, they'll have spiritual ones. You're going to have to have a plan around route of this canal that takes into consideration many of their sacred sites and other concerns.
That said; Australia's outback is VERY big [citation needed]; so big in fact that there have been suspected nuclear detonations in our outback that people have only noticed as a couple of bright flashes here and there. Many of these places are effectively unpopulated, even by the Aboriginal communities. Why? Well, because there's nothing there to support human life. It's too hot, not enough water and food, etc.
Getting agreement to use an area to build new cities and farming communities in such areas might be easier than you think, especially if some of the (newly arable) land is dedicated back to the Aboriginal community.
As for water and canals, you might not need to go as far as you think for it. The Great Artesian Basin could supply a lot of the needed water so long as it can be extracted (say from northern South Australia) and if necessary, piped over to the NT/WA border somewhere for your new 'colony'. So long as you can get the water there and then start some agriculture in the heat, you'd probably do quite well, at least to begin with.
Ultimately you're still going to need sustainable rainfall in an area; the Artesian Basin won't last forever if you're pulling the amounts of water out of it that I think you'd need. That said, there is some precedent in doing this kind of work. A quick look at Israel tells us that it's possible; the next thing would be to find a way that works for Australian conditions.
(This part is out of scope of your original question of course, but I didn't put an answer on the previous question so I'm going to town here a little.)
Ultimately (like a lot of things in Australia) the answer to your question is ultimately one of personality. It depends on how you approach the decision makers, and what their immediate and long term needs are. If you have an unlimited bucket of money to do this, then it's very doable. As for the economics of securing the land; well again (like a lot of things in Australia) that may have a lot less to do with money and a lot more to do with respect.