I'd try good earplugs first, earplugs and your headphones next, earplugs and noise protection ear muffs next.
A simple $25 test is to get Laser Lite foamies and Leightning L3 earmufs. That's the best you can do without a helmet in actually blocking noise. If that's good enough you can optimize for comfort/size/style from there. If not, then try tricking yourself by pumping white noise through headphones on top of earplugs.
Personally, on planes I use http://www.howardleight.com/earplugs/laser-lite foam earplugs. 32 NRR. Any drug store or Amazon in bulk. You can still hear people, but even crying infants don't bother you much. And they get rid of engine noise. Most comfortable earplugs I've found. You need to learn how to put them in properly. Good enough NRR that when you open your mouth it gets noticeably louder.
When shooting I double up and wear MSA Sordin Supreme Pro-X upgraded with gel seals over earplugs. Get the neckband version. http://www.srstactical.com/communications/electronic-ambient... Sordins are 20 NRR by themselves. Probably 35NRR over earplugs.
For indoor handgun shooting I like Howard Leight Leightning L3. http://www.amazon.com/Howard-Leight-R-03318-Leightning-Shoot... 30NRR and extremely comfortable. Probably 37NRR over earplugs. They are big enough to cover a lot of area around your ears. When doubled-up you can't understand other people and can barely tell they are talking.