I don't think you necessarily need a high volume. I think you just need enough that's statistically significant for whatever you're testing. And like another commenter noted, google optimizer is free.
To reiterate what I meant about costs. For sure Web Optimizer is Free, but the software isn't the only thing you need, for multi-variate testing you need many variants of the item you want to change, you somehow develop without directions,which can be very time consuming and (maybe) expensive.
On the other hand you can also have direct usability testing for free, think family, friends (I would use my mother, because she is a user who is interested in the Internet in general but not very tech savy)
Most definitely, otherwise you are really just eye-balling it and you don't want to find out that your small sample-set wasn't representative of your actual user-base.
This is important considering that during early stages you could have early adopters and other more tech-savvy types using your site more heavily than what you will end up with.
You don't necessarily need to give people a specific task.
For example, just ask them to discover the site, watch them in what they do, watch what they spend their time with, discover which problems they have while surfing your site. As always this can, of course, only be a part of your whole testing effort. Watching people solving tasks is also important.
Additionally I have to say, that I am not against A/B or multi-variate testing, in my experience it just is very time consuming (and therefore expensive) and the effort to get results is bigger than with direct testing IMHO. If you think you have the money or have exhausted the possibilities with direct usability testing, A/B or multi-variate testing is a valid option.
On the other hand you can also have direct usability testing for free, think family, friends (I would use my mother, because she is a user who is interested in the Internet in general but not very tech savy)