You've pretty much answered your own question there (except that you don't absolutely need a long exposure, it depends on the situation). The key ingredient is obviously the particulates in the air to reflect the light, but in the shot you've posted also the extreme exposure difference between the incoming sun and ambient light. The greater the difference, the fewer particulates you need in the air as each one will be shining brighter, and the better they will show up against a dark background.
Some post processing will probably help too. The photo you posted has always bothered me as it looks a little fake, I wouldn't be surprised if a little dodging went on in the darkroom to increase the brightness of the light shafts.
Here's an example of the effect caused by haze and precipitation in the atmosphere which I enhanced a little in Photoshop to emphasise the effect:
To do this is a church you might need to ask them to turn the interior lights off to maximize the difference and then wait for the sun to shine directly through a window. Overexpose the shot to best reveal the shafts of light.
To reliably replicate it, assuming you're already cut the power, most churches are quite dusty so you could run around, beat the carpets and pew cusions a bit. That ought to put enough dust in the air to get the effect you're after!
disclaimer: don't acutally do that last part
edit: You're still going to need a lot of dust or very strong contrast to get the effect you want in a church - here are a couple of shots from a recent wedding. Note how much brighter the light from the window is (I even had to darken it in the Raw conversion, the difference was greater than it looked) and yet it's not enough for any shafts of light to be visible: