A real & important question, but by no means an impossible problem. E.g. suppose "the public" (e.g. gov't, as with public lands) owns all of it in the first place, sells it, and uses the proceeds to fund water projects.

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.