Over the last few months, I've had two family members that ran into that situation.
What they ended up doing was upgrading their iCloud storage to 20GB (for US$0.99/month) and enabling iCloud Photo Library, which freed up a significant chunk of space on their 16GB devices.
Now they're "amazed" that they can see/edit/organize all of their photos on a web browser on any computer via www.icloud.com that I doubt they'll upgrade to a 64GB iPhone next time around and will just keep with iCloud Photo Library instead.
Just be sure they back that up really well somehow. Apple's cloud track record is pretty bad.
Also, unless they've fixed it, Apple's cloud photo capability is limited to the smallest device's storage on the OSX side, as it syncs everything.