This is a topic that gets people really bent out of shape. Seriously!
However, my opinion is that anyone who doesn't think playing to a click is a good idea either a) doesn't have good enough timing to do it or b) hasn't really worked in a studio before.
I've been recording for about 15 years, in an my opinion, clicks are necessary to getting really tight recordings in a multitrack setting, especially in songs with breaks that require everyone to come in at exactly the same time.
If you have the facilities, technique, and equipment to record everyone in the band simultaneously where you can all visually cue off each other, you may be able to get away with not having a click. Other than that, I'd STRONGLY recommend using a click.
If your song changes tempos, it's a simple matter with almost any drum machine to program a click that will change tempos where the song does.
Eighth note clicks are MUCH easier to follow than quarter note clicks in most cases, but if your song's really moving along, eighth note clicks get annoying.
Use something higher pitched like a cowbell or a calave and you'll find it cuts through things better and is more difficult to lose.
Be sure to have the click only as loud as you need it, and also that you have decent sealing headphones or else you'll end up hearing click track picked up by vocal mics, overhead and tom mics, and especially
acoustic guitar mics.
If you're (and especially your drummer is) not used to playing with a click, take the time to rehearse with one for a while prior to recording with one. We usually run a drum machine into a channel of the PA at our rehearsal studio and play with a click as a band for about a month before we go into the studio until you stop even hearing the click because it becomes second nature.
Good luck!
CT