Thanks again Nuxwin.
So we could figure out that if you have the google two factor authentication enabled and you update joomla, e. g. from 3.6.2 to 3.6.3, it would break the login. It then shows the mentioned 500 Internal Server Error.
I don't know why it broke directly after I enabled the "Verzeichnisschutz" and not after the Joomla update, but maybe it triggered some kind of a Joomla cache refresh.
I will open a Joomla bugtracker. Until they provide an answer or a fix you can fix it the following way:
Disable the two factor auth within your database. To do that, you have do open pma, go to the *_extension table, search for plg_twofactorauth_totp and set "enabled" from 1 to 0.
You can now log into the backend with your username and password, the secret key field stays empty. You have to re-enable the two factor auth plugin via Plugins.
Then you have to disable the two factor auth in your user account settings and delete the secret key generator for your site from the Authenticator App.
Finally you can re-enable the two factor auth in your user account settings and configure the Authenticatior App.