You have to have a payment method (i.e. credit card) from the other country, even if the apps you want to download are free apps.
You can go into your iTunes account and simply change your country, it will prompt you to enter the other payment information as well as a new address.
It's kind of a huge pain in the ass, as whenever you want to update those apps (or apps from your previous country) you have to switch back and forth and re-enter all that information.
Also, if you're thinking of being clever and just using iTunes gift cards from the other country, be very careful - iTunes WILL NOT let you change your country back if there is any balance remaining on the gift card.