I am wondering if there are any good rules of thumb for how to go about selecting an approximate inference algorithm for a problem/model (specifically when exact inference is intractable)? When you are faced with a problem, what are the things you consider when selecting an approach for inference (e.g. MCMC, belief propagation, variational, etc.)?
At first you have to decide what amount of time you can afford.
In case you have a large amount of time for your numerical experiments you can try MCMC method, also in this case it is possible to avoid complex integrations in some cases.
In case you have a strong background in statistics and you want to integrate a lot you can try methods like variational lower bound or expectation propagation. So, you have to choose carefully a batch of parameters (for example, in case you try a variational lower bound approach you have to select distribution you can integrate out to replace initial distribution, so you have to use your intuition (or use normal distribution)).
If this problem is new and no other approaches were tried you can simply try to use gaussian or Laplace approximation.
Also, in many cases yo can use a method proposed in the state of the art. For example, all methods you mention were successfully used to proceed heteroscedasticity gaussian processes regression (see, for example paper http://www.tsc.uc3m.es/~miguel/papers/vhgpr_icml.pdf from the 2011 ICML conference).
P.S. In ICML 2012 article http://icml.cc/discuss/2012/360.html interesting and simple method for variational inference was proposed, so you can try it for your problem.
I think that there are no universal solution. So, I try yo give a couple of general advices.