This scene does not imply that Stone Men do not breathe.
In the scene in question we see multiple Stone Men jump from the rocks above the boat--two into the water and two into the boat directly. Jorah and Tyrion (but mostly Jorah) fight the Stone Men off, knocking them repeatedly into the water after the Stone Men repeatedly jump or climb into the boat. When Tyrion finally falls into the water, he is grabbed from below by one of the Stone Men who had fallen into the water previously. He is grabbed about ten seconds after the most recent Stone Man is knocked into the water. I was able to hold my own breath for the entire 90 second duration of the scene without much trouble. By contrast, the Stone Man who grabs Tyrion could have been holding his breath for as little as ten seconds, depending on which of the Stone Men he was. That he grabbed from below and pulled Tyrion down suggests that Stone Men tend to sink and cannot swim well--the fact that the Stone Men Jorah kills do not float to the surface supports this--but the scene in no way implies that Stone Men do not need to breathe... In fact, Tyrion's survival suggests that the Stone Man who had him, let him go for some reason--most likely because he drowned.