I've done this several times, renting a flat in Berlin for some weeks up to about a month. Over the years, my platforms of choice have been wg-gesucht.de and zwischenmiete.de. The first one of those had more offers than the second one when I last used it in December 2012. A lot of offers were available on both platforms.
On these platforms you find apartments or rooms by people who are away for some time. For example there are students studying abroad for a semester, and they decide it's better to sublet their place for some money than leave it empty. You can get pretty good deals if you are lucky.
I recommend getting in contact with people by phone. Also, often it's not worth considering offers older than three days, but you never know.
The full price is usually comprised of:
+ utility costs (normally fixed)
+ deposit (normally up to a month base rent)
I estimate for around 600 EUR per month, you should be able to find a decent flat in any district of Berlin. Availability, of course, depends on the time of the year. At the beginning of a University semester, it can be hard to find something.
Airbnb may be a useful addition:
You can use it to bridge some days, until your preferred place is available.
The references in your profile are an important asset also outside of Airbnb.
Concerning Airbnb, some general advise: Look for places that are a little above your budget, then negotiate.
You may also want to check ImmobilienScout24, which I presume is the market leading online platform for finding real estate in Germany, at least as of 2013. Immowelt is a competitor. Note, however, that normally apartments offered on these platforms are for long term rent. Most of them are unfurnished. Furthermore you may have to show a proof of income when applying.