Distorted .obj Export
The problem with your mesh are Ngons; Blender can process and show them correctly but once exported you get unexpected results because they are treated in a different way by another program. 

This is what model looks like:



The reason why it worked with Triangulate faces checked is because there were no Ngons any more, all them were converted to tris. You can use this way, however you won't be able to control how it will triangulate faces.

Hence I suggest to start with changed topology of the model (note: it may be a bit complex to redo for all the model, however it will save time further on):