This is where Google's Play Music works much better - your music is in the cloud by default, but you can "pin" specific albums to have them stored on the device.

If you play some song that's not on the device, it will be streamed and then cached for some time till space runs out.