Audio Technia AD-700 + a Zalman clip-on mic. The sound quality will be better than any comparable headset, and the two combined will only run you about $110.00+shipping. The AD-700's cans have very soft velour pads that are intentionally made to sit on your ear and insulate the sound. Unlike what you see in headsets, this material is canted inward and is soft enough that there is no pressure on the outer ear. Additionally, they are open backed which prevents the pressure buildup of closed-back headphones that irritates some people's ear canals, and helps give them a wider sound stage.
Personally, I'm in the same boat as you. When headsets or headphones rest on my outer ear it gets very painful very fast. The AD-700's (and also Beyerdynamic's headphones just to fairly mention them) have so soft and pillowy that I have never had any irritation from the pads resting against my ear.
If you're skeptical about the recommendation though, you can always look for a pair of circumaural headphones (or if quality isn't a big concern for you, headsets even), but quite frankly these are often closed-backed for the sake of preserving bass. For me, I don't want heavy bass when I'm gaming because it muffles footsteps, and closed back headphones irritate my ear canal.
The vast majority of high-quality headphones instead go with the soft velour pads that are very thick, and the feeling is very much like laying your head sideways on a pillow but with less pressure. There is no ridge to provide irritation.
Here is a post from Head-fi (an audiophile site) that discusses many different models of headphones ranging from sub $49.99 all the way to $1000.00. The AD700's are included in these short descriptions:
http://www.head-fi.org/t/534479/mad-lust-envys-headphone-gaming-guide-updated-12-28-12-astro-a50-added