Question: I have an iPhone 4 with iOS 7.1.2 (latest available for my phone apparently). I have about 500 contacts on my iPhone, however only 203 of them appear on iCloud.com. I cannot get the rest to sync with iCloud and you can imagine that manually re-adding about 300 contacts, one by one, sounds rather terrifying. I tried all the tips I could find, i.e. turning off and on the "Contacts" in the iCloud settings on my phone, logging off iCloud on all devices, restarting my phone and Mac, etc. Nothing changed.

Answer: 
It's likely Apple can support you with iCloud if your account has a problem. Before calling them, though you will want to check and see under the Settings app what you have configured under Mail, Contacts, Calendars.

It's entirely likely your iCloud contacts are exactly what <https://www.icloud.com/#contacts> shows.

1. Make a backup of the phone to a computer if possible
2. Make a backup to iCloud for safety
3. Then inspect all accounts. Write down each account that has contacts synced.

You can disable iCloud contacts on the device and tell it to delete all those contacts from your phone. You will then be left with contacts on the device itself and other cloud services. Check them similarly (log in online) and then disable syncing. At the end, you will have contacts that exist on the phone only.

Sync them over the computer and get them into iCloud or enable iCloud only for contacts and choose to merge things.

That usually sorts things out.
If you have only an iCloud account, it is probable that the contacts that don't appear there are local i.e. On your phone only. 

To upload them, do the following:

1. Go to Settings > Mail, Contacts, Calendars
2. Select your iCloud account
3. Find the "Contacts" switch and turn it off; it will ask if you want to keep the contacts on your phone or delete them —select keep
4. Wait till it's done
5. Turn "Contacts" on again for iCloud; it will ask you if you'd like to merge existing contacts with iCloud —select yes or merge