Can't store contacts on my Android phone
Based on what you wrote above, 99% you cannot restore your contact. No google account literally reduce your chance to restore contact. I am sorry.

Next time, please backup your phone. The simplest backup IMO is a google account. Your contacts, app, calendar will sync to google account. You don't have to use your personal gmail for your phone. Just create another gmail for your Amazon fire phone. How to sync your personal email and Amazon file phone gmail is another question.

Please mark as answered, i am collecting points. thanks