Would a native speaker say 'I was frozen out of fear'?
No, “I was frozen out of fear” is not a natural way to say that fear had frozen you into place. “I was frozen to the spot”, on the other hand, is natural enough. Also consider “I was paralyzed with fear” and “Fear froze me to the spot”. But avoid saying “I was paralytic with fear” unless attempting humor.