I'm moving around the EU a fair bit at the moment. First in the UK was fine - I was able to open a bank account with just a passport and a mailing address. Having a local bank account made life a lot simpler while there.
Then I moved to Sweden and tried to open an account there. You need a residence card, proof of home ownership or rental contract, a Swedish social security number ("personnummer") which in turn means you need to be able to prove the right to live there for at least 12 months, proof of employment, they want to know the ins and outs of your expected income and where you'll be transferring money to/from, etc etc etc. It took nearly 4 months in all.
What countries in the EU are the easiest for opening a bank account? It doesn't need anything like a credit card, overdraft facility etc, just basic savings, ATM card and online banking.