1. Figure out what earplugs work well. Working well means good sound suppression but also means earplugs that you can have in your ear comfortably for long stretches. I can sleep the entire night in the ones I settled on (I buy them bulk: http://www.amazon.com/Moldex-6800-Pura-Fit-Soft-Earplugs/dp/... ).
2. Get over-the-ear headphones, the kind that physically enclose your entire ear. Mine are noise-canceling as well but most of the benefit comes from the enclosure.
3. Play a white noise mp3 into the headphones. Turn the volume up to the point where you can just hear it through the earplugs you're also wearing.
With that setup, I would not even notice people talking next to me. People would often have to wave their hand by my laptop screen to get my attention (to ask me to share the coffeeshop's power outlet or what not).
I rent an office now and am happy that is not a daily situation for me, but that's how I made the best of it after much experimentation.