Forum Moderators: open
There are companies out there that will do it right for a relatively small amount of money.
This kind of thing can do far more harm than good if not done properly, I strongly suggest taking the high road here and get the client to pay for a service like this. Have them look at the demo presentation, they'll most likely be blown away and get out the checkbook. :-)
You don't absolutely need the blue or green though as any decent editor will be able to key out any solid color. Find yourself a solid color wall, make sure your subject is not wearing anything similar in color to the wall or they are going to disappear too. The imporatant thing here is to eliminate shadows on the wall so you need a lot light on it and diffused light on your subject.
Once you get a video taped for starters you can use Ulead Video Studio for editing, they have a free trial. That's about the cheapest program I'm aware of with the ability to do green screen. Once you bring the footage into the program you'll have an option somewhere to selct the color you want to key out of the video... no more back ground color.