One private room per team works very well for programmers without the expense justification. The two most productive jobs I've ever had in an office were with that arrangement, not cubicles or open offices.
I have no issues with NC headphones could even sleep with them, it has pretty much become a part of me.
For you. For many others (myself included), using NC headphones is even worse than putting up with the noise.