[hocuspocus]

I had no issue signing up for internet with 1&1 for two years, and got a free SIM card in the process.

As for credit cards, that's pretty common, traditional banks want to see your salary landing on your checking account for a few months before they issue you a credit card. Comdirect gave me a prepaid VISA in the meantime.

Anyway I ended up using a debit card (the MasterCard from N26) for almost everything, and later on I got a Gold credit card from Advanzia (I believe they do get information from the Schufa, but you also start with a pretty low monthly limit and need to prove them you pay your bills before they raise it).

[kuerbel]

You really shouldn't use N26. I don't know if they have improved the security of their app during the past two years, but here is a talk from 33c3 https://media.ccc.de/v/33c3-7969-shut_up_and_take_my_money

It's worth watching. They show how they where able to take over accounts and such.