Use tactics that have been successful in reducing smoking
In the United States, smoking tobacco has been on the decline. This New York Times article explored how the most effective methods involved decreasing access to cigarettes (especially due to finances) and limiting public exposure. Also, these were gradual changes over time, not an immediate ban as happened with the US alcohol prohibition.
Educate people about advertising tactics used by the industry, with the goal of giving them a negative perception of it
But educating people about the tobacco industry’s marketing efforts can have a big impact. “We now have empirical evidence that people who don’t like the tobacco industry are about five times as likely to quit, and a third to a fifth as likely to start,” [Dr. Stanton A. Glantz] says.
Anecdotally, I see this technique used heavily in my area, with an ad campaign of "big tobacco targets kids" to create a negative perception of the industry.
Ban the substance in public locations
[Dr. Glantz] also notes the importance of smoking bans. “When you create smoke-free workplaces, bars, casinos and restaurants, it sends a strong message that smoking is out,” he says. “It also creates environments that make it easier for people to quit smoking.”
Also, fine those who violate this
[Dr. Mary O’Sullivan] says that many of her patients who are trying to quit head to city parks, where it’s been illegal to smoke since 2011; people caught smoking in parks face a $50 fine.
Reduce substance use in movies and other popular media, and increase negative portrayals
According to these experts, also at play may be increasingly graphic ad campaigns, including the “Tips From Former Smokers” campaign begun last year by the Centers for Disease Control and Prevention and fewer incidents of smoking in popular movies. Research shows that the more times a young person sees smoking in the movies, the more likely he or she is to take up smoking, and from 2005 to 2010, young people saw far less smoking in PG-13 movies. (Many of those youths are now adults and would have been captured by the new report, though smoking in movies has since increased.)
Stuff that needs more research
Increase the price of the substance at retail locations via taxes
This has been a very effective tactic for reducing smoking, but you said that it had already been tried for alcohol. More research needs to be done to see if this would work if the other methods listed above were implemented.
Richard Grucza, an associate professor in psychiatry at Washington University School of Medicine who studies tobacco policy, cited the 62-cent-per-pack federal tax increase that took effect in 2009, as well as laws that ban indoor smoking, cigarette vending machines, the sale of packs of fewer than 20 cigarettes and the distribution of free cigarettes, as major contributors to declining smoking rates.
In other words, increasing the tax, outlawing distributions of small quantities, and banning official distribution of free cigarettes worked together to make it more expensive.
and
[Dr. O’Sullivan said,] “In New York, we’ve gotten it down to 14 percent, and one of the big reasons is price. Here it’s $12 a pack. Even our schizophrenia patients, who are the most addicted, who used to smoke two and three packs a day, even they are smoking less because of the price.”
Stuff that probably won't work
Don't rely on school education programs
These turned out to be less effective than other methods.
School education programs, for example, don’t appear to be very effective, most likely because schools are difficult places to change social norms and it is hard to do the programs well given all the other demands in the school day, [Dr. Glantz] says.
Also, to my knowledge, there are no current efforts to prevent someone from growing their own tobacco or consuming it on private premises. These tactics were not effective for prohibition of alcohol in the US, so a society trying to reduce alcohol consumption would do well not to try.