Is there any way to stop Z-fighting besides remove doubles?
No, I don`t think there is another method to get rid of z-fighting. If remove doubles does not work, try increasing merge distance in the input field that appears after using remove doubles:



As for weird shading just try to get your normals right. Toggle into Edit Mode, select all faces, then hit Ctrl+N in order to make the normals consistent. For those faces that did not get fixed, try flipping their direction by selecting them and clicking flip direction in Shading/UV tab of the Toolshelf (T):