Is it possible to estimate a substance's water solubility from data like the substance's partition coefficient, dissociation constants, etc.?
It could certainly be estimated from those properties, the structure, etc.  A lot of companies have developed proprietary algorithms for things like that:  solubility, diffusion coefficient, polarity.... (For example of a company, see "ChemAxon")

The water solubility for many chemicals is already known, though.  Search for a chemical ChemSpider, and look under the "Properties" tag.  

They've even got an API, in case you're interested in using water solubility in an app.