This from MoDaCo worked for me:
Using the Amazon Appstore from outside the US (including paid apps)

The gist is you need..

1. An account with amazon.com (rather than .co.uk or whatever)
2. A valid US address and phone number to attach to this account
3. A US registered credit/debit card number for the account attached to account's 1-Click settings

Legal and 'non-illegal' methods given in the link.

This from MoDaCo worked for me:
Using the Amazon Appstore from outside the US (including paid apps)

The gist is you need..

1. An account with amazon.com (rather than .co.uk or whatever)
2. A valid US address and phone number to attach to this account
3. A US registered credit/debit card number for the account attached to account's 1-Click settings

Legal and 'non-illegal' methods given in the link.

Update
This method no longer works as Amazon seem to have started checking your region (IP address presumably). So looks like you'd need to use a US based VPN now.

This worked for me:
Using the Amazon Appstore from outside the US (including paid apps)

The gist is you need..

1. An account with amazon.com (rather than .co.uk or whatever)
2. A valid US address and phone number to attach to this account
3. A US registered credit/debit card number for the account attached to account's 1-Click settings

Legal and 'non-illegal' methods given in the link.

This from MoDaCo worked for me:
Using the Amazon Appstore from outside the US (including paid apps)

The gist is you need..

1. An account with amazon.com (rather than .co.uk or whatever)
2. A valid US address and phone number to attach to this account
3. A US registered credit/debit card number for the account attached to account's 1-Click settings

Legal and 'non-illegal' methods given in the link.