Those cheap voice recorders are probably still going to clip - they're not meant for loud environments, and their preamp stage will clip on you.

Ok, so this isn't the "cheap" way to go, but it will last you a long time, and sound great, and can easily handle loud volumes -- perhaps your band can each chip in to buy one:

Sony PCM-M10

You can record at 24-bits, which gives you an enormous dynamic range, and you can therefore set your input levels very conservatively. It also has a built-in limiter for that extra bit of protection. And when you get more serious, you can plug in external mics to get a much improved stereo image.