Completely clear all cloud music from iPhone
The most recent version of iOS I have used is 7.1.2, but in that version you have to go to Settings>iCloud>Account Name>Delete All Data, and then sign out. It still may not fully work, so you should also log in to your Apple account in your browser (or go to Settings>iCloud if you have a Mac), open the list of devices associated with your account, and remove the iPhone. Finally you may want to change your account password to make sure the device cant be auto added to the account when it reconnects to the internet.

I will be the first to agree that their forced integration of iCloud and refusal to let you remove it is crap. For this reason I might also recommend jailbreaking if you're okay with it. Once an iDevice is jailbroken you can install iFile and manually delete the songs from the iCloud music folder. Be careful though because deleting the folder itself could cause problems.