If you wanna go the VS studio way, I'd prefer to buy a used VS880 or even better a vs880EX on ebay. Both machines have a hard disk inside, which allows you to use better recording modes with less audio compression artefacts. I found them for down to 300€ on ebay or in these private advertising papers...
I second the opinion of NOT buying a 4-track; it simply isn't good for anything...
We play in a punk rock/thrash pop band and used 14 tracks at our latest recordings.
5 tracks of drums
2 rhythm guitars
2 accoustic guitars
bass
lead guitar
additional guitar
lead voice
background voice
This would be killing you on a four track with no v-tracks...
OTOH, some of these newer four tracks with flash cards might be very convenient to transfer to PC, so you could record your drums to the box, add bass and rhythm guitars and transfer the whole thing to the PC, do a rough mix there and record the next 3 tracks the next rehearsal... But I'd go for a vs880 or vs880ex. They're transportable and have decent sound quality. If you buy a 840, tkae care for it being the 250MB version...
Oh yes, one more thing: I'd DEFINITELY go for a machine that has some 'nice' effects in it. It's much more expensive to use external effects and you will need them after a short while. If it has some compressors - even better. You WILL need them to get a decent 'full' sound. If you record everything through an external compressor, you may get along without it... Oh yes, look for the EQ. Even though the Roland EQ is said to sound rather unmusical, it is still better to have such one than to have one with fixed settings for high mid and low frequencies and/or Q...
Ciao,
aXel