You don't need a nose to breath. I was unable to breath through my nose till I was nine years old (I had an operation to cure this problem). I managed to stay alive for nine years, even if I couldn't smell anything.
Mudokons do have nostrils. I saw them on one of the Mudokon's skull, which are right above their eyes. These can be seen in the copyright images of AE, right before the game begins. Didn't you see the skeletons?
If the mudokons have their nostrils above their eyes, then their skulls must be similar to the ratz. It's still odd that their nostrils aren't visible at all.
I guess it's one of the mysteries of Oddworld, and it probably won't be that important in future, unless OWI show how Abe breaths in a future movie/game.