Camera settings are never going to make this easy. Photographs need light to work, and while modern sensors are actually quite sensitive, they can't live up to our perceptions, because our brains take the dark, noisy image from our eyes and subconsciously make a mental model where the imperfections aren't noticed.

You don't mention what lens you are using, but one thing you can do is to use the widest possible aperture — and possibly even get a faster lens. The kit lens that comes with most cameras tends to be very slow, particularly when zoomed in. (That's because these lenses have variable max aperture, and usually about 2½× faster at the wide end.)

One very popular Canon recommendation is the 50mm f/1.8, which you can get around $100. (Other brands have similar lenses, although the Canon version happens to be a spectacularly good deal.) At 50mm, this will let in about 10× the light of the kit lens at 50mm. (However, it will also have very shallow depth of field, which may or may not be good for what you want.)

Another possibility is to bring light. Depending on when and what you're photographing and whether you're doing it by request or with official permission, you may be able to set something up using flashes. Cavernous churches don't make getting nice lighting easy, but this may be better than nothing. If you have the ability to set something up, spending a few hundred dollars on remote-triggered flashes could make all the difference.

Finally, you might want to reconsider what "grainy beyond repair" means to you. You note that you're shooting in RAW, which should give you fairly wide latitude in noise reduction. If you're not making gigantic prints — that is, 8×10" or smaller, or viewing online without zooming all the way in for no good reason — you actually should be able to get quite acceptable results at ISO 6400.