Actually a couple video players right now do make this choice available to the user - OPlayer and AVPlayer. They both say something to the effect of "Backup media" in their settings. This simply toggles which location the media is stored in (AVPlayer even seems to move the media on the fly).
This is literally exactly how I would implement the choice if I were Marco.
The problem is if the user chooses not to backup the data, it'll get wiped if she runs out of storage space. What would be nice would be to not sync to iCloud AND not get cleaned out.
This is literally exactly how I would implement the choice if I were Marco.