I tried to load a free app, but as I have moved to Spain from the UK it wouldn't accept it. I had to change my Google password and I have tried to change my address from my iPhone but it won't let me.
Often, if you can't download (even free) apps from the App Store, this is because your payment information is not valid (or no longer valid).
From the Settings app, go to the App Store settings, then tap on your Apple ID in blue at the top. After typing your Apple ID password, tap on Payment Information and make sure all the data is present, and correct.
Also - you had to change your Google password? I am confused by this ...
You mention changing your Google Password from your iPhone, so I'm not sure if you are really talking about your AppleID password (for the iPhone App Store) or your Google Play password. My answer assumes you really mean the AppleID.
Apple has a separate App Store for each country. Many apps are available at multiple App Stores, but some are limited to specific countries' App Stores. To use the App Store for a given country, you need to have a Payment Method for that country. This can be a credit card, or an iTunes card specific to that country. If you need to use an Apple Store in a country you aren't in, and don't have a credit card for, you can get a friend or relative to buy you an iTunes card and email you the code. You may also be able to purchase an iTunes card for that country on eBay. You CANNOT use an iTunes card from one country in the App Store for another country.
You can load apps from multiple AppleIDs (and thus, multiple countries) onto you iPhone at one time. It's a bit of a pain, and best to keep one as your "main" AppleID and only use the other for apps that absolutely require it, or you'll end up being switched back and forth a lot and it gets messy.