Between big commercial banks and savings banks, online banks (comdirect, ING, DKB, ...) and challengers like N26, I've never met anyone who had trouble opening a bank account. Americans didn't have access to some non-essential investment products thanks to FATCA, but that's it.
Some online banks outsource this process to the Post: https://www.deutschepost.de/en/p/postident.html
I'm not sure how N26 does it these days, at the time it was over videochat. I believe it's just a picture of your ID and a selfie now?
However, while you need a German address, no registration is necessary (which I'm only having done on Monday). I didn't even have any German phone number yet at that point.
Don't you need a bank account to transfer money into N26? As far as I know there is no way to deposit cash into any of these disrupter service providers.
AFAIK it's the only challenger bank to support doing something like this for free, even in a limited amount. Even Bunq, which I pay for, doesn't support it (https://together.bunq.com/d/2933-how-do-i-deposit-money-or-t...).
§31 specifically states that anyone with legal residence in the EU must be allowed to open a "basic" account. Occasionally banks will list this as a separate offering from their normal account, but they really should have told you about that. Sorry to hear they didn't.