I want to know how far I could overclock a FX-4100 with the stock heatsink.
Silicon lottery. Every chip is different so it is very hard to tell you the precise megahertz numbers. With the amd fx cpu's you need to invest in a quality motherboard to get good OCs.
I wouldn't advise you go more than about 15% of an overclock. So about 4-4.1 GHz may be safe. Just buying a replacement tower cooler would be a massive improvement, I typically recommend going for the 140mm fan compatible models if your case will accommodate it. With a respectable tower cooler, you may be able to achieve 4.5-5.0 GHz. Expect to spend about $80 on a cooler capable of taking you to 5 GHz.
Totally depends on your thermal output, and how much you want to put up with a fan that sounds like a jet-engine when you reach max loads on your cpu.
I got 4.2 GHz on my stock cooler, just had to put new thermal paste on it when I OC'ed it. That was more likely because the card is two years old and I only OC'ed it 5 months ago. I only touched the multiplier and upped the voltage. Using prime 95 it gets to about 67c, gaming around 50c, and idles around 20c. This result seemed pretty typical online, but results may vary. Just do small increments until you can't get it any higher or are comfortable with the result. You won't really know until you try.
I've gotten 4.32 ghz on the stock cooler. I have 8 gb of ballistix ram 1600 mhz, AsRock 960GM/U3S3 FX mobo. At idle it sits at 14 C. I have stepping enabled =D