In many ways this would be similar to how Foursquare rolled out.

Perhaps you can identify scouts in particular cities who have expressed their delight in your service or create a signup page for people to get notified when you arrive in their city.