After about an hour of searching and debugging I've found the answer:
The FritzBox password can only be digits.
For future reference, these are the complete steps:
Create a new telephony device here: http://fritz.box/fon_devices/fondevices_list.lua (you will need to log in to your router). Choose Telephone in the first step and LAN/WLAN (IP telephone) in the second step.
Pick a random password that is only numbers. Advised length is 16 digits because hackers can guess numbers more easily (a strong password should have letters, but the FritzBox cannot do that with for VoIP/SIP).
Tip: after entering the password in the fritzbox, copy it to notepad and format the numbers into groups of 5 to make them easier to type into your Android device.
Using 16 random digits, you can safely enable the "Allow registration from the Internet" feature in the "Account Information" tab in the FritzBox.
Look your IP address up using a site like http://whatismyipaddress.com
Select "Receive incoming calls" in Android, even if you disabled it in the FritzBox. This is temporary and makes it easier to test.
Use the settings (the important settings are bold):
Username: 626 (or whatever account number you got)
Password: your password (numbers only!)
Server: your IP address
Authentication username: not needed
Display name: as you like
Port number: 5060 (default)
Transport type: TCP
Send keep-alive: Automatic (default)
If you enabled "Receive incoming calls" in step 5, then the device will now try to register so that it can start receiving incoming calls. You will see the account status change (we're still in the "SIP accounts" screen).
When it reads "Receiving calls", it means it is currently ready to receive calls. This means it could contact the server and the login worked.
You can now, if you want to, disable "Receive incoming calls".
Calling via this internet account should now work!
Troubleshooting at step 8:
If it reads "timed out", you probably mistyped the IP address or DNS address. And make sure that the transport type is set to TCP. If it's set to TCP already, try UDP instead, but it's probably TCP. You can also try using
fritz.box instead of the IP address, but that will only work at home (not elsewhere).
If authentication failed, you used a password with letters (or spaces or something else). Or you mistyped it. Or you have the wrong account number. Or maybe you mistyped the server's IP address (you might be logging in to the wrong FritzBox!).
Note: If you have a dynamic IP address (an IP address that changes every few days), you will need to use a dynamic DNS service. I have a static IP address (you can sometimes request them for free at your ISP) so I don't know which ones are good nowadays, but there used to be plenty of free ones out there. In this case, use your DNS address instead of your IP address as server in step 6.