I think they should sign a contract with McDonald's or Burger King - a company that has a vast, global network of drive thru restaurants already located along busy roads. It would be a huge win-win.
Tesla: get access to a network of exisiting, busy locations world wide, where people stop for 20-30 minutes anyway to take a bite. These locations have parking lots, some of which could be easily converted to Superchargers, so they could really fast track building the network. The restaurant chain would give the space for free, of course and cross promote Tesla raising awareness. Did i mention this would be global? There is only so many strategically well placed rest stops along busy roads - it wil get difficult getting access on their own.
Restaurant chain: huge opportunities to market themselves as green, e.g. would go very well with McDonalds' current re-branding. Could also cover the roof of the restaurants with solar panels and advertise that they use those to power the restaurant when no one is charging.