The best solution - I think - is FONIC (
FONIC -- Das ist die Wahrheit.). You may get a Sim at Mediamarkt, DM (drugstores), Lidl (supermarket chain), Jet (gas stations) ...
They are in the network of o2-de and offer an (almost) unlimited Internet access. The settings are easy: APN (Zugangspunkt) pinternet.interkom.de, user empty, password empty. There are two tariffs: Unlimited internet access for 2,50 EUR/day or 24 ct/MB. You may change the tariffs by sending a e-mail to customer care. For registrations you need to tell them (a) a passport number and (b) a german address.