Registering German prepaid cards
Theorectically all German Prepaid Cards have to be registered. Practically you can buy SIMs from the network operators at some kiosks and call shops that don't require you to register them, but these are the exception. Most cards can be ordered online as well, however most obviously you'll need a German address to receive them.
T-Mobile, Vodafone, BASE and O2 SIMs can be bought at the respective stores. At least in largers shop there should someone speaking English, you have to register the card when buying, however registration is possible using a foreign passport.
Aldi cards can only be bought at Aldi stores. They have to be registered online or at the hotline, in either case you need a German ID. (You can't buy them online, at least not yet.)
You can buy Penny Mobile prepaid card at any Penny Market discount store, then you have to activate the prepaid card at Pennymobil.de, you don't need a German ID (or any other ID for that) to register your card.
You can buy Smobil prepaid card at any Schlechter discount store or online at Smobile.de. However unless you pay with a German EC-Card you are required to show a German ID.
You can buy Rewecom prepaid card at any REWE, miniMal, toom, toom BauMarkt or Petz discount store, then you have to activate it at Rewe-com.de, you don't need a german ID (or any other ID for that) to register your card.
Tchibo cards can be bought at Tchibo coffee stores. In larger cities you might find someone speaking English, you have to register the card when buying, registration is possible using a foreign passport though the exact handling depends on the shop you are visiting though.
Simyo, Blau.de, Blauworld: These cards are bought via internet but shipping is only possible to German addresses. They are usually available also at Saturn and Media Markt stores.