Nagi has his vocal cord removed during his back story. In the majority of the story, however, he talks freely. Some deadmen show extreme healing abilities. Did he regrow them? He was being courted by a group in power. Did they pull strings to have them replaced? Note that I have watched the anime but not read the manga. I kind of expect the answer to be there.
This is from the Nagi Kengamine Wiki page:
Equipment - Soundboard: He has a soundboard installed into his mechanical voicebox. It allows him to make special sound effects, including but not limited to: air horns, clapping, and a rape whistle. Due to Genkaku hijacking its system, it also glitches so that all output turns into his moaning, much to Karako's shock and dismay.
So it appears that he has a mechanical voicebox. That also explains why he has a robotic voice. The technology is believable when you consider the scene where he pulls the little cell phone from his tooth in order to alter Minatsuki's penalty game to try and convince Ganta to join them.