Country/region change in App Store on iPhone
You will probably not be able to change country via your device due to this reason of it asking you to add CC details.

Your next option is to log into Itunes on your pc change your country and there it will give u the "none" option .

Now if u dont have that option available then u have an outstanding debt on your account from a previous purchase wether it was the last thing u brought or something previous to that. You need to clear the debt first by either adding new cc or buying a gift card adding it to the istore and the amount owing will automatically be deducted. 

Thanks ,  hope this helped