Europe doesn't have to be so expensive, you know. And hostels are NOT particularly cheap in either Europe or the United States.
There are furnished apartments on craiglist.com in berlin for €25/day or €360/month, for example.
I recall renting a nice hotel room in Paris last year for €23 (single only and no TV) but the cheapest hostel there is about €15. Two years ago I rented a really lovely double hotel room, with TV, in Paris for €30/night but the cheapest hostel was €13/night that year. €13*2=€26 for 2 people, so it really makes no sense for a couple to stay in a hostel, unless they really like sleeping in crowded dorms. In San Etienne last year I found a nice hotel room for €20, with TV.
In both Zamora and Santiago, Spain, I recall paying €10/night for a nice rooms w/o TV (I prefer w/o TV actually). If you are willing to stay longer term, you can easily find places for under €200/month.
The situation is similar in the United States. In San Francisco, which is one of the most expensive places in the world, you easily can rent nice furnished hotel rooms for under $200/week (including all taxes) but the cheapest hostel with crowded dorm room costs about $25/night, or the same price. For long term stays, there are decent hotel rooms in San Francisco can be found for under $600/month.
The main thing is not to be constantly on the move. That is what really drives up costs in both the United States and Europe--this frantic buzzing about from place to place.
If you really enjoy buzzing about from place, then you should do what the locals do--which is stay in campgrounds. Of course, that will be difficult for you because of all that heavy gear you are carrying. Bicycle or car touring from town to town and staying in campgrounds is how the native Germans and French manage to enjoy traveling without spending a lot of money.
I was just in Berlin. I cannot recall the name of the stop, but one of the U-bahn stops says "Checkpoint Charlie" on the wall under the stop name. Hope this helps!