It's not your travel that's restricted in the EU; it's your right to work.
That's true - like foreigners need a green card to work in the US.
Still, many airlines hire and employ people at their major destinations, which could be the case here. That's why they speak of unrestricted travel and not of citizenship of an EU - country. Therefore drop an Email to your next German Embassy and to Lufthansa as well - their should be a link on their website. The recruiting people are used to questions like this, so don't be shy.
Concerning the costs: Sending them the application will not cost you that much - JUST DO IT! Maybe they even offer standby tickets or you do not have to come to Germany, when LH is hiring abroad. Again, this information can be provided by LH.
Concerning the language - you do not need to be perfect, but learning a language in school only will most likely not allow to follow the tests / training, if they are done in German. As mentioned before, you will also have to speak German in an emergency situation - and I can't imagine a school which will be able to teach you that. Therefore you should consider to train ANY foreign language with native speakers (in your case in Germany, Austria or Switzerland) - some weeks are worth years of studying. When I am in the US or Australia, after about a week I start to dream and think in English.
If you are really interested in some kind of student exchange, I might be able to dig out some information here in Vienna. There are many exchange programs available for the US and the UK - I think it should be no problem to find something the other way around.
Regards, Bernhard