I don't have a google account, nor a windows computer with outlook.
I am running iOS 9, and my iPhone was linked to my work's Exchange server (2010 - version 14) with all my personal contacts.
I bought a new Macbook and wanted to link my iMessages on the Macbook to my phones contacts, but I didn't want to link my personal computer to my work's Exchange server.
So...these were the steps I took to move my contacts from Exchange to iCloud.
Log into the Exchange server's OWA web interface (Usually https://your.exchangeserver.com/owa )
Click on the Contacts on the left side.
On the right hand side should be your list of contacts. Select a bunch of them (I had to do it in 3 bunches because it complained when I selected too many). Right click and pick 'Forward as Attachment'. It attached all of them as individual attachments, 1 .vcf each. I sent the email to myself.
When I got all the emails, I saved all the attachments to a directory.
Now...on the phone, in the Settings App->Mail,Contacts,Calendars I went to my Exchange account and turned off Contact syncing. It told me it would delete all my Exchange contacts on the phone, and when I accepted, it did.
So, now I had no contacts.
On my MacBook, I logged into iCloud.com and clicked on 'Contacts'.
From the Finder as a test I dragged and dropped a single .vcf file into the 2nd pane from the left (where the list of contacts is). It imported fine.
But dragging and dropping more than 1 always gave me an import error (the error message was something like "bad data in field").
I didn't want to import 188 files, one at a time. I wanted to do them all at once. From reading on the Web, I suspected that iCloud could import more than 1 record per file, so I concatenated them all into 1 file.
To do so, I opened a terminal and changed directory to where I saved the .vcf files. Then I ran this:
cat *.vcf >> all_contacts.vcf
Then i dragged all_contacts.vcf into the iCloud.com contacts list pane, and it imported all 188 perfectly. Even the photos of my contacts.
On my phone, I went to Settings App->Mail,Contacts,Calendars then picked the iCloud account. I enabled syncing of Contacts, and they were all there.
Hope this helps.