Start with a "Einzelunternehmung". Registering that takes 15 to 30 minutes at your local mayors office and costs 30 Euro. From there on you can make something like 20k Euro turnover per year, if you grow out of that, you can still "invest" in a GmbH or whatever suits your needs best.

On the other hand, if you are sure that you're building the next Facebook, getting the money for a GmbH together on day -1 should be no problem at all. It turns out that most companies don't make it that far, though...