First off make your life easier:
1. Download the "remote" app for your iphone https://itunes.apple.com/gb/app/apple-tv-remote/id1096834193?mt=8. Then you can start entering your password using a proper keyboard. It's a disaster via the apple remote. The remote app lets you navigate and enter text using your phone
2. Write your password down so you can easily copy and paste it into the box (then obv delete it afterwards)
Now how to get it working:
1. Go to Apple ID settings on the web (https://appleid.apple.com/account/manage and switch off 2-factor auth (it's an option in the security settings)
2. Go to your apple tv and sign into your itunes account (using your iphone app to make it easy)
3. (because you want to be secure) go back to apple and switch 2 factor auth back on again. MAKE SURE YOU ADD A PHONE NUMBER FOR CONFIRMING AUTH CODES
4. Now that you're logged into your TV try to buy something (cheap)
5. It'll ask you for an auth code and whether you want it texted to you or via a device. CHOOSE THE TEXT OPTION. If you get it sent to your device it's 6 digits long and doesn't work. The text option is 4 digits long and does work
6. Input the code that gets sent to you and you *should* be in.
After many round loops this worked for me. The key was getting the 4 digit text token rather than the 6 digit device token. If you want to make life super easy just leave the 2-factor authentication switched off but given that Apple has your life you're MUCH better off keeping it on.