Massive operation to both kill all caches and ensure the filesystem is healthy: Plug the phone into iTunes, and do a local encrypted backup. Restore the phone. Choose to restore the backup when prompted.

Reason I bring up the filesystem health aspect, the iPhone uses HFS+ like the Mac. It's pretty dated, and can at times lose track of how much free space really exists. Thankfully Apple is replacing the filesystem in the future, but not likely till iOS 11 in 2017.

Messages, you are correct they aren't stored in the cloud in a readable way, would break the privacy and secure aspect of them. Odds are attachments may be chewing up a lot of space. If you go into a message thread, and then tap details in the upper right, all past attachments are visible when you scroll down. Press and hold on one to get a More option, and you can mass save them out, or delete them.