My dad was having the same issue with his 8 GB iPhone 4S. He has a Mac Mini, but it's too old to use iTunes to update it to iOS 8, so I tested a theory on my son's iPhone that is identical and it WORKED! I didn't have to clear anything off his iPhone either. He had 840 MB of space available and after the iOS 8 update, he now has 1 GB available. I have successfully updated an 8 GB iPhone 4S to iOS 8 OTA (over the air) without connecting it to a computer or using iTunes.
It sounds counterintuitive, but you have to first back up to iCloud then erase, then set it up as a new phone, then erase it again, then restore it from the iCloud backup. It takes a while so be prepared to walk away. I think I managed to get it done between 1 to 2 hours. It will depend on your internet speed. iOS 8 has been out for a few days, so it should be available from the server consistently by now.
Some things to be aware of: after you do an iCloud backup, go check what's actually in that backup because there may be some apps in there you had deleted to save space, but they will get put back onto the iPhone again even though you deleted them. You may have to toggle them off in the iCloud backup. Just make sure that what's actually backed up in your iCloud backup is exactly what you want to come back onto your iPhone after you restore it.
You will need:
- sync/charge cable and power source
- internet connectivity
- your Apple ID and password
- Your Wi-Fi password
- Apple ID password for store purchases in case you share an Apple ID with a family member
- About 2 hours or less
If you have these stored on another device in a password manager, great. If not, write them down and be prepared to key them all in manually.
GOOD LUCK and let me know if this helped you!