My contacts were linked to an iCloud.com account and not my gmail.com account. I only created an Apple ID with my gmail account and have no idea how that iCloud.com account was created. Now my contacts got deleted and I only have the password for my gmail.com account but my contacts are not synced to that account. My contacts are synced to the iCloud.com account and I don't have the password for that account.
Your iCloud account was probably something you created when you bought the phone or updated. It's part of the Find My iPhone feature that prevents your phone from being used by someone else if it's stolen.
You need to regain access to your iCloud account, using http://iforgot.apple.com is a good start to reset your password.
You should check your iPhone Settings app in iCloud to see if Find My iPhone is enabled, if it is you will not be able to disable this without the password, and if you ever have to restore the phone again you will require this password.