The cheapest (as in 0€/month) plan would probably be a SIM from Netzclub, but that's financed via advertisements.
And then there was Congstar's "Prepaid wie ich will" (the 1st generation), which offered a "free messaging option" (1 GB / month, but only 32 kb/s) you could book every month. You just had to keep the SIM alive by topping up your credit by 15€ every 15 months (iirc). The unthrottled data options for this plan were expensive though.