What is a good measure of the difference between two probability distributions other than Kullback–Leibler divergence?
I suggest you take a look at this question. In the accepted answer there is also a link to a very good survey which mentions more about a dozen metrics between probabilities. There are also discussions which metrics are useful for which problems, and results on the comparisons between the metrics (e.g. which one bounds another etc.). The computability questions are not covered there, since it is rather tough to give a general advise on how to compute them - but there was also a paper on Monte-Carlo methods to compute some of these metrics. If you are interested, I can look it up for you. Please, specify your request if you had some particular question in mind.