Go to
Settings --> iTunes and App Store --> Apple ID: youremail@blahblah.com
Click on your Apple ID. Hit "View Apple ID". Type in your password.
Now you'll want to tap Country/Region, then Country or Region.
This is where it gets a bit complicated. I think the easiest region to fake an address for is Canada. Select Canada, then agree to the Terms and Conditions.
Select "None" as your payment option. This step is key. You can change it back later.
Now fill in your billing address. Use the address I'm giving you. It's fake AFAIK. I found it on a website that explains how to write Canadian addresses. The only parts you need to fill out are:
Address (first one): 22 Knightbridge Road
City: Amprior
Province: ON - Ontario
Postal Code: K2S 0Z7
The postal code needs a space.
Go hit next and you're done! You'll get an email from Apple saying you updated your address etc, and you can immediately go to the App Store and download Hearthstone! Have fun. I certainly am.