We have the same issue with my wife's iPhone (16GB is just too small these days). What we ended up doing for her was a little kludgy, but it works.

First we installed Dropbox on her phone, which syncs every photo and video in her camera roll to their service. For us, this also syncs it to our Synology NAS. Whenever she runs out of space on her phone, she scans her Dropbox folder to see that everything made it into there, then we delete everything from the phone. At this point she'll also move the photos to a more permanent folder on the NAS that's seen by Picasa.

This frees up storage space on her phone and gets a good backup, but unfortunately it means she doesn't have any photos to show people. We might set her up with iCloud like Tom suggested, but she doesn't use iCloud for anything else, and she does use a lot of Google services and is running somewhat low one GMail storage, so we'll probably just end up increasing her Drive storage and backing up photos to Google Photos.

In the end, we could simple install the Google Photos app and leave Dropbox out of it, but I like having the local backup too.

The most challenging part of the process is always deleting the photos from her iPhone. It took a while to figure out that I have to go to collections, and I'm able to select groups of photos instead of individual ones. It's a little quicker but still not really fast enough.

On a side note: Google Music All Access has a really annoying storage behavior. It'll store a cache of recently played songs, but that cache gets HUGE! My wife recently ran out of space on her iPhone again, but it hadn't been long since the last "purge." I found that Google Music was taking up around 2.4GB of space! I have no clue why they'd feel the need to cache that much stuff.