For future reference for all those who find this thread which should not end with “nevermind, I’ve fixed it” but no solution.
I still dont know what caused the problem, but I deactivated 2FA for the whole server, reinstalled the addon, activated 2FA for the server and on my account again and finally was able to connect the android app as always.
So all the apache header settings were correct but already active via htaccess and the real problem was somewhere in the 2FA addon. I am running this server since Nextcloud 10…