Make It Illegal to Pay
The more this happens and more financially lucrative it becomes, the more convincing the argument for making it a crime to pay ransomware becomes. I would probably also make it a crime to pay the criminal not to release stolen data. I just don't see any other practical way to make a major dent in this racket - there are just too many businesses, governments, etc who are potential victims.
I realize this may not be a perfect solution, and would require many countries to change their laws, but I just don't see a good alternative which is likely to happen.