Можно и без прописки, но нужен тогда postalische Adresse.

Да и то, не каждый филиал почты захочет заморачиваться, если прописки нет в документе удостоверения личности.

Короче, как повезёт.

Für Personen, die über keinen festen Wohn­sitz bzw. eine melde­recht­liche Anschrift verfügen, ist es möglich, eine Prepaid SIM-Karte auf legalem Wege zu erhalten. Verfügt eine Person über keine Adresse, kann diese nicht erhoben werden. Wenn eine Person - wie in Ihrer Anfrage geschil­dert - über eine Adresse verfügt, unter der sie posta­lisch zu errei­chen ist, jedoch nicht gemeldet ist (sonst stünde die Adresse ja im Perso­nalaus­weis), ist diese Adresse vom Diens­tean­bieter zu erheben und zu spei­chern. Eine Über­prüfung ist dann natür­lich nicht möglich, da mangels melde­recht­licher Anmel­dung die Anschrift nicht im Ausweis einge­tragen ist. Hier gilt: Was nicht möglich ist, kann nicht verlangt werden. Der Gesetz­geber hat unter anderem Reise­pässe zur Über­prüfung der Rich­tigkeit der Angaben zuge­lassen. Reise­pässe enthalten jedoch keine Angaben zur Anschrift des Inha­bers, eine Anschrift kann also anhand dieser Doku­mente nicht über­prüft werden. Es ist daher zulässig, die vom Kunden ange­gebene Anschrift zu erheben und zu verwenden, auch wenn diese nicht anhand eines Ausweis­doku­ments über­prüft werden kann. Es wäre deshalb auch zulässig eine Post­fach­anschrift zu erfassen.

https://www.google.com/amp/s/mobil.teltarif.de/amp/prepaid...

А купить уже зарегистрированную симку (как это было легко сделать раньше) сейчас можно только в какой-нибудь турецкой забегаловке. Да и то под очень большим вопросом.

Других вариантов нет.