I hate open office plan environments. I feel very lucky to work from my own home office full time now. That being said, I've done my time in open offices. Some things to try:
- Try saying "No" to interruptions. This is probably better worded as "Sorry, I'm really heads down on something right now - can you shoot me an email about it, or maybe I can come find you later?" Do that enough, and people will grow out of the habit of constantly interrupting, because there's no reward.
- Develop a signal for your coworkers that indicates you're in "heads down" mode and that you shouldn't be disturbed. When I worked at Google, one of the SREs had a sign on his desk that said "If Cody is wearing the rockstar glasses, he is thinking and shouldn't be disturbed". I've also visited offices that have sliding whiteboard doors on their cubicles, and the office policy is that if the whiteboard door is open, you're fair game to interrupt, but if it's closed, you need to be left alone.
- In ear headphones may be better than noise canceling, if you haven't tried those. I have a nice pair of shure's (SE210's) with these tips, which are pretty similar to earplugs: http://compare.ebay.com/like/290692040848. I also had custom molded earpieces made, but I could never get one to make a good seal. The other one was great though, so it might be worth a shot.
- Try coming in early or staying late. Any time spent when the office is more empty will likely be more productive.
- Hide:) Conference rooms are good, and out of the way couches or stairwells sometimes work.
As someone who is way more productive in quiet environments with minimal distractions, I wish open plan offices and "bullpen" environments weren't so trendy among startups.