Most smart phones are locked to a specific network - they are subsidised by the network
You can buy unlocked ones, but they cost a packet. I just checked the wholesale price of a Samsung Galaxy Nexus and its £441+ VAT, so the retailer is going to put another 10-20% on that. Same company had some Nokias going for £350+ but I'd steer away from those given Nokias current problems
You probably will need a new SIM card - many of the older ones can't handle data
As for roaming - take a look at T-Mobile, I believe they offer globally priced contracts