I moved to Berlin almost three years ago, and extended/expanded my company here. I am not a start-up, though I am developing a product, but more of a one-man consulting shop.
Getting a self-employed VISA is not easy unless you have some serious credentials. My partner has three degrees, two post-graduate, from highly regarded US universities; an extensive profile of speaking engagements; a very, very solid financial standing; and a solid business plan. The IHK (who reviews all business plans for self-employed applications) still said "No" but begrudgingly gave the green-light when presented with a book contract from a well known technical publisher.
I have no degrees, but a financially viable consulting business of some years, and a lengthy professional background. Three years later, over 12 foreigners office appointments, a UG (affectionately known as the mini-GmbH) with over 12K founding capital, a high-priced lawyer, over a 120K in USDEUR transfers, and a visit from the police to confiscate my passport over Christmas, my self-employment visa is no further along than the day I first submitted it.
Still, incomparably better than US immigrations. I'm certainly stuck in some weird, exceptional state that has confused even my lawyer.
Consider Berlin. It is wonderful here, definitely. Rents are rising, however, and (sadly, in my opinion) you do not need to learn German. I know of far too many people who have spent numerous years here without speaking more than a phrase or two of deutsche.
If you want to start a company/be self-employed DO NOT follow the (typische amerikanische) DIY process. Factor in costs for tax advisers and lawyers.