I'm somewhat disturbed by the proliferation of short links outside their original motivating uses, like print and social messaging. As it is, bit.ly does various sorts of tracking, but in general, short links add a variable to the chain and and increase the susceptibility of breakage over time; or worse, changing in a bait and switch move.
But if it's relocation to anywhere not-China, then yes, that ought not to be too difficult.
And, Google just needs to get the people out of Mainland China. If their safety is in danger for actions that they had no control over, I'm sure some country will give them asylum.
Or maybe China realizes that it lost, and will model the rest of the country after Hong Kong. (Remember, Hong Kong is technically mainland China.)
The Chinese people cares house, education and health care more. Most of them don't use Google at all.
Google's chinese marketshare disagrees with you: http://gs.statcounter.com/press