Is there any free software available for green-screening? I prefer Linux, but Windows is also fine.
Depends on what your definition of good green screen is.
In terms of free software to do green screen well...Only one that I can even think of that does keying is Da Vinci Lite which is free from blackmagic's website. It is pretty complex and pro based, but with a little searching around you might find what you want. I am not sure if you can technically do green screen with it though.
If you don't mind learning there is a tool that has them all, green screen, video editing, 3D, compositing...
The name's Blender