Ok, point by point. Full disclaimer: I'm not Indonesian, I'm from Singapore, a city-state neighbouring Indonesia. However, I have been to Indonesia multiple times (more than just Batam/Bintan) and have some experience in jungle living in Brunei.
Budget: I would be travelling on an extremely tight budget. Very tight. If i will have a few hundred euros available after flight/insurance/visa/equipment costs i´ll count myself lucky. I´m fully prepared and willing to deal with any inconvenience arising from this. Thankfully i don´t plan on doing anything touristy, surfing or diving related.
Budget isn't likely to be much of an issue at all, considering the exchange rate of rupiah to euro. If you truly don't do anything touristy you can maybe get by on 100 euro a day.
Information about myself: 24 years old, white, german, male. Blue hair. (How strange would blue hair be for indonesians?) small tattoos on the right arm and leg. Physically fit enough. While strictly speaking not one, i´d identify as a buddhist while travelling indonesia
Blue hair is strange for rural Indonesians, which will probably be all of those you'll interact with. Regardless, Indonesians are mostly very nice people, so there won't be trouble ... except if you self-identify as Buddhist without knowing much about it. Seriously, wtf? Pretending to be another religion to fit in = big no no.
1) Food and sustenance. I´m used to fasting, doing it in prepartion from time to time, and can also live on humble rice basically forever. But considering indonesias famous fertility i actually imagine that it would quite often be possible to forage some fruits and vegetables from my surroundings. (Ofc, i don´t want to steal someones harvest. And ofc i would inform myself about edible plants before i do this.) Am i right in this assessment? Basically i´d plan carrying some rice and a cooker with me, supplementing my diet with some cheaply bought or foraged plants. Is this a viable setup?
Sorry to break it to you, but foraging for food is not actually enough to survive on if you haven't been doing it for years and have experience. And bringing a rice cooker? Where do you plan on getting electricity if not stealing it? I would strongly strongly suggest buying food instead.
2) Travel and accomodation. My dream would be to travel around the country, mostly on foot. I greatly enjoy walking and also wish to see the countryside. I could bring or acquire a tent and would mostly be comfortable sleeping outdoors. Are there laws in place, which might hinder me? Is there a decent couch surfing community active in the larger cities? If i wander the countryside and would come upon a small village, would i be able to find accomodation there? For that matter- How densely populated are the rural areas of indonesia? If i set out to walk a whole day through the countryside could i expect to chance upon a village/town? Will i be able to hop from island to island with little cash?
No idea about local laws w.r.t. camping, but you may wish to take into account the climate difference between Indonesia/Germany when buying a tent. No idea about couch surfing. Likely no accommodation (in the sense of a hostel) in small villages, but you may be able to pay to sleep in someone's house (if you're comfortable with that). Not very densely populated at all, compared to Germany. Island hopping with little cash possible if you pay a fisherman to bring you around, but beware getting scammed and not ending up where you want to be.
3) Wildlife. Hailing from germany my only experience with dangerous wildlife was one night when we chanced upon some boars in the forest. However, this doesn´t compare to the wildlife of indonesia- Tigers, elephants, rhinos, various snakes, scorpions, mosquitoes and even giant lizards. Considering i´d like to travel around the countryside i feel a bit anxious about this part. What are your opinions on this matter? I don´t think it´s a nice experience to meet a tiger or get bitten by something venomous in the middle of nowhere. Are there ways to minimize the risks? How dangerous exactly are all those poisonous/venomous creatures? Could i count on finding life-saving treatment in time? Is it possible/viable to get and carry some medicine/antidote with me?
Tigers are extremely rare (I think endangered?), so are elephants, rhinos; the fact that you're worrying about them shows how unprepared you are, worry about saltwater crocodiles instead. Poisonous fauna and flora are much more dangerous, but not many are all that life threatening ... except if you're backpacking alone and have no one to help you if you do get bitten. Do not carry antidotes and try to administer them yourself, for the love of god. Nearby medical facilities should carry relevant ones, with the added benefit of having actual doctors.
4) Mosquitoes. Should i get a vaccination against malaria, or only carry some pills with me? What about dengue?
Malaria vaccine is ineffective, get pills and take them regularly instead. Dengue is not that serious when treated, and there's a vaccine but that may be out of your price range.
5) The wet season. I´m aware that the rainy season starts right when i want to travel. How much of a hassle is this, really? I´d reckon that rain might actually be quite nice in this tropical area. Again, i´d like to travel around the countryside so the hassle might be quite a bit bigger than i´d expect.
It will make your nights very miserable if you're staying outdoors, and if you're travelling on foot.
6) Carrying a staff. I practice staff fighting, and would like to continue with this even while travelling. (Besides, considering that i´m travelling alone it might just give me the security i need in dangerous situations, when common sense and running away fail me.) I doubt that there are any laws in place to forbid the carrying of a staff, but i ask just in case. Also: are there martial arts using a long staff (My staff of choice is 1,80 m long) being practicied in indonesia, which i could probably check out?
No laws against staves, but if you think you can adequately defend yourself with one you're mistaken. How well will you and your staff do against 2-3 guys teaming up on you with parangs?
7 ) Language. My language skills consist of very good spoken english, very good german and a smattering of latin. Obviously i would try to get as proficient as possible with indonesian before starting my trip. What other local languages i should check out?
THIS IS A BIG RED FLAG. While it's perfectly possible to get around Jakarta or Bali not knowing a single word of Bahasa Indonesia, out of the tourist areas and cities, you will not be able to communicate in any meaningful way. You will likely be getting scammed in every transaction, and I have no idea how you're going to get transport or directions to anywhere from the locals. As for other local languages, Indonesia is a hotspot for linguistic diversity which I don't know much about. Malay is basically the exact same language with some pronunciation differences, though.
8 ) Islands to visit. I´m still unsure which places exactly to visit. Ideally i´d like to check out everything, but that certainly won´t be possible. The Malay peninsula and sumatra are probably a given. Java/Kalimantan and Sulawesi would also be very nice. I´m also curious about ternate, tidore and halmahera, but those small islands might be too far out for me. Some opionions about which islands i should definitely visit would be nice.
Honestly, you should probably stick to Sumatra and Java. Also, Malaysia is not Indonesia.
9 ) Earning money on the fly. Considering my small budget, i will almost definitely run into money troubles. So- Is it viable at all to earn some money on the fly in indonesia? I don´t have any particular skills or craft, apart from my fluency in english and german.
No, absolutely not. As you said, you don't have any skills, so it's just manual labour or odd jobs, which will absolutely not cover your expenses. And in any case, most people won't hire a foreigner who doesn't even speak their language.
10 ) Safety. Are there any areas which might be particulary dangerous for a lone traveller? Any no-go areas? Places with high unrest? What about corruption and bribes? If i have to bribe, what is a good amount to give- And in which situations?
I would say everywhere outside of a city is dangerous for a lone traveller, but specifically for unrest, avoid Papua and Aceh I guess. And do not offer bribes, unless you will literally be arrested, sentenced and convicted without recourse to your embassy. You'll probably be paying a lot of unintentional bribes anyway if you don't know the legitimate prices of things (and can't ask).
11 ) Flying. Oh boy. I have never flown in a big aircraft before, so i´m kinda anxious about this part. I have heard some horror stories about unsafe indonesian airlines, so are there any you can recommend? Any especially good airports where i should try to arrive?
Garuda (the carrier you've probably heard about) is okay these days. You may wish to try budget airlines like AirAsia or Tiger Airways, but I don't know if they fly to Germany, most are just regional. You may try flying to Singapore (shameless plug) Changi Airport, then transferring to a budget airline to Jakarta or elsewhere in Indonesia, though.
12 ) Anything else you can think of. Really, any information or hint or warning is appreciated.
I reckon that as long as i have enough money to fly back when i can´t stand it anymore and as long as i don`t die, i have nothing to lose. I appreciate the answer, but without any reasons given it won`t help me.
I would strongly advise you to not do this. If you must, try Thailand or Vietnam instead, both are much more conducive to backpacking. Why did you even pick Indonesia, if I may ask? What are you hoping to gain out of this trip, soul-searching? Trust me, there are much better ways to do that, try backpacking in Europe.
Your cavalier response about having enough money to fly back and 'as long as i don't die' really underscores how unprepared you are. What if you end up robbed and don't even have enough money to make it back to a city, let alone fly back? Or if you get bitten by a snake and are too weak to walk to the road? Or if you wake up and discover that the rain swept away your belongings in the night? The doing it alone part is really the most impractical component of this endeavour.
Anyway, I realise that my curt answer up there wasn't really polite, so sorry for that.