The best advertising would be to get as many merchants as possible to offer it as a payment option on their websites or at the register in bricks and mortar stores. The benefits of bitcoin would then sell thenselves.
Yes the key is getting proper legit business onboard, 'teentrepreneurs' starting small shops are great but pushing established businesses across to bit coin is a massive boost.
Having reliable infrastructure, services and exchanges who deal with fiat actually having the required licenses is another thing to concentrate on, before worrying about population coverage