And credit cards in Germany are not "credit" cards as well. At least the one I got from Sparkasse does not let you hold a balance and must be paid in full every month.
Not sure about those, but I got mine around 2-3 years ago from gebührenfrei.de, which is from Advanzia Bank. Seems fine so far…with a minor disclaimer that I don’t really use it much. :-)