I'll disagree with Andre somewhat on this. I looked at purchasing an unlocked Motorola Razr phone online to replace my dead one. The phones were reasonably priced. When I read reviews, however, there were far too many saying the phone either didn't work at all or wasn't unlocked. If either is the case, the phone is no more than an expensive paper weight and you have to buy a phone in Europe anyway.
It's easy to find something in the 25 euro range that includes phone, charger, SIM card, and usually ten euros of call credit. If you have the clerk set the phone up before you leave the store, you won't have to worry whether you can use it or not - and minutes in the country you purchased the SIM are cheap. The only down side is having to visit a store to add minutes (seemed to be true of Vodaphone and Orange). If you travel through multiple countries, use up your minutes then get a new, local, SIM.
The cheap phones are basic, they aren't smart phones. So plan to use your tablet for other things. WiFi is widely available in hotels, restaurants, and bars.