SIM cards are not required for cellular connection. They are just some sort of ID method.
For example: If a phone has AT&T SIMCard, the configuration in the SIMCard will let it connect to AT&T as an identified (with phone number) user and so the SIMCard can be billed for the usage of service.
However, even without a SIM, a phone will always try and connect to cellular networks. But it will be a, let's say, guest user who can't use any of the services since they can't be billed because they can't be ID'd.
911 however is an exception. All services allow 911 calls regardless if the client is identified or not.
I told all these so you can understand the conception better. Now for the actual question: It probably can be traced without a SIM as well. Why probably? Because I don't know for sure nor have I ever heard/seen such a case. But conceptually they should be able to do it since they can also access your phone's IMEI and therefore identify the device and triangulate its signal. It is not something you can do on your own though, it is FBI-class action.
It is completely unrelated to GPS because GPS uses satellite, triangulation uses cell.