It will be very difficult, if not impossible to get even a half decent key out of that kind of footage. The only way really to do this is to use a mask and individually "cut" or "mask" the actor out of the shot and then put you background video or image in.
This way is more manual, takes much longer, and will not look quite as great. If the project isn't that important (and you have a lot of time on your hands), this may be a decent solution. If not, if it is important or you have little time, reshoot the footage. That may be best. And in the futurte, use blue screen when you have green clothing, and vice a versa. Or just don't wear green
Hope that helps you out.
P.S. How different are the greens? Can you upload a little footage or just a screen shot, maybe I could take a look at it for you. Some of my handywork with chroma keying cvan be found on the tutorial forum here.