Currently I got an Asus Xonar soundcard and Superlux headphones with a Modmic attached to it for about 80$ and I bet the actual mic and sound quality are above what you can get with any "gaming" headset in that price range.
I can concur with this assessment. From everything I've read, all of those components are top-notch.
I have my eye on the
Superlux HD668B, which is supposed to be a nearly identical-sounding knock-off of the Audio-Technica ATH-AD500X. (The best price I've seen it go for is under $40, but it's still a good value at $45.)
I should point out, though, that this set is open-back, so like the Sony mic below, if you're using it for gaming you'll want a quiet room/environment around you.
Anyway, for adding a mic to that, yes the
AntLion ModMic is the best way to go, but it's expensive ($50).
If you want optimal sound quality, I'd get the
Sony ECMCS3 ($20) which is a stereo omnidirectional mic that can clip onto your shirt's collar or something. The downside there is that it would likely pick up more room noise than you would want, so for gaming, it's probably not best unless you can have a quiet room.
There's also the
V-Moda BoomPro ($30), which is meant to be a side-arm boom-style mic add-on to headphones that have detachable cords. The Superlux above has a detachable cord, but the end on the headphones is male whereas the BoomPro expects female -- so you would need to get some sort of very small F-F coupler to make them work together, and even then, the mic might flop around a little due to the flexibility of the little pigtail coming out of the headphones. This mic is a fairly popular option, but its sound quality is just average.