A less radical option would be to keep the system of water rights we have today and simply allow the water to be bought and sold. Currently if you sell it, someone can take you to court & say "well you didn't use it, so you should lose your water rights" (because California follows the doctrine of first use). Would run the risk of creating wealthy water czars overnight, but less radical.
I have no idea how first use could work for water, would be happy to read more if you link me to something about it. A quick googling returned nothing.
The last one requires a lot more specifics to talk about meaningfully, but I'll bet that most of the free marketers wouldn't consider it a free market.
So one way of looking at the whole problem is to ask why transaction costs are too high to make this feasible. And the obvious answer is politics.