I've had the same problem, also know how to change imei but knew it was illegal but I asked at a local police station and phone shop if there was a loop hole. They both asked for the proof of purchase, the police told me aslong as I own the phone with the imei I plan to use and that both phones are not in use at the same time then it was ok to do it, I'm guessing thats so if the phone is ever tracked by police they dont get 2 seperate signals/locations. The phone shop told me its not advised due to the risk of damaging the phone but if I was to do it then all warranty is void. I'm stil sat with a blacklisted s4 as the imei I could use is now my sons phone which is in daily use
Sent from my GT-I9505 using xda premium