I understand the concept in libertarianism that if corporation A dumps toxic waste in a river and downstream of this river corporation B bottles this water for consumption, that corporation B has had its property rights violated and thus can sue corporation A for damages.

There is the case, however, of Chlorofluorocarbons (CFCs) which were phased out under the Montreal Protocol - which along with the related Kyoto protocol were the first universally ratified UN treaties. These chemicals, used as refrigerants, had been shown to be causing a hole in the ozone layer over the antarctic which could have spread across the globe.

If, under a libertarian model, a person is responsible for their infringements on the property rights of others, yet the results of an action are spread across the whole globe and intractable, how, if at all, would the person or company be held responsible? The real-world response of a global commitment by all states to regulate the use of such a chemical seems antithetical to the libertarian model.

Same way CFC problem was addressed. As you will notice if you look at the detail of the issue (e.g., this blog post - which is overall very pro-regulation and pro-environmentalism and aggressively anti-free-market), CFC regulation by the government happened after the CFC market shrunk more than 75% already. In other words, 75% of the problem was solved by means that were arguably within Libertarian tool-set - publicity, etc... - even before the "official" libertarian tool-set (tort lawsuits against offenders) were engaged.

You will note that this isn't a singular example. Same libertarian-acceptable approaches worked for many other negative externalities: obesity-causing companies (fast food, junk food) have changed their product offerings due to education campaign of their customers.

For completeness, there are two main types of libertarian approaches:

1. 
   

   Make sure people are aware of the externalities.

   
   
   

   Then, the externalities become costs via social pressure (brand damage; people preferring competing products that don't have same externalities - e.g. electric cars vs. carbon fueled cars).

   
   


2. 
   

   If the externalities are provable, use lawsuits for damage.

   
   
   

   If a specific harm can be proven, the sources of extrenalities can be sued for that harm. That imposes costs on externalities as well - both legal risk and financial cost if the lawsuit is lost.

   
   

Economic foundation for this can be found in the Coase theorem (discussed in detail in @lazarusL's answer). See this UCB paper for a specific examples.

Why do property rights solve pollution problems? The answer comes from an important economic idea called the Coase theorem. Very simply, it states that if bargaining costs are zero, then an economically efficient resolution to any externality is possible by assigning property rights regardless of who you assign them to. A more detailed explanation can be found here. Property rights as a resolution work well when bargaining costs are low. For example if a wind turbine is imposing loud noises on a lone farmstead nearby it will be easy for the turbine and farm owners to negotiate whether the turbine operates. If the turbine is near a neighborhood and the property rights for noise are given to the turbine owners it may be very difficult for the neighbors to pool their resources and negotiate to buy back the rights to a quiet area. Even if they collectively value the quiet more than the profits of the wind turbine the coordination might be too costly to coordinate for an efficient outcome.

The chlorofluorocarbon example presents huge bargaining costs. Every person in the world has to be concerned about a growing hole in the ozone layer and many people can manufacture or use chlorofluorocarbons. Many libertarians might admit that this is too difficult to bargain and just assign responsibility to a regulatory body while still being biased towards assigning property rights in situations where bargaining costs are lower.

One libertarian option is to issue tradeable pollution permits. Private Environmental groups can then bid to buy these permits and prevent pollution from happening against companies that wish to use them to allow their factories. This option still involves significant government action as setting the number of pollution permits to is a big task that would have to be undertaken by the state.

Another option is to assign property rights to the people broadly and then litigate against the companies with a class action lawsuit. Lawyers could produce evidence for ozone layer depletion and then if they win, force polluters to pay damanges out to every citizen of the country. The legal system could assign damages according to common law understandings that would continue to pay out according to the rate of pollution. Many libertarians admire common law approaches to resolving externalities.

In terms of international policy, there is nothing inconsistent in a libertarian country taking action to protect the property of their citizens. If the property of local citizens is threatened by chlorofluorocarbon producers abroad, a libertarian government might be compelled to apply pressure legally, economically or even militarily to protect its citizens' property.

If someone was concerned about this impact (and no generous billionaires step up to fix it out of the goodness of their hearts) they'd first need to be able to quantify and qualify said impact in a way in which it can be attributable to individual sources. They'd have to fund that research themselves, with few hopes of an ROI for their labor. Once they could prove beyond a reasonable doubt that it was Exxon with the Oil in the Caribbean Sea (and its impact in dollars), then they'd task whatever bare-bones contract enforcement police exist to collect from Exxon. Repeat ad nauseum with each organization causing world-harm, or at least until the concerned individual ran out of money.

Very much what user4012 said, but there are other ways to convince and coerce people and corporations to do the right environmental thing.

http://www.businessinsider.com/greenpeace-fortune-500-deforestation-global-warming-2014-6

The Inside Story Of How Greenpeace Built A Corporate Spanking Machine To Turn The Fortune 500 Into Climate Heroes

[They] unfurled a pair of 60-foot-tall banners on the front of each tower. The banners denounced Head & Shoulders, the antidandruff shampoo, for "putting tiger survival on the line" and "wip[ing] out dandruff & rainforests."

The problem is the aggressive manner in which the world's biggest palm-oil producers, based in Indonesia, have gone about meeting demand: burning and clear-cutting the nation's priceless tropical peat forests to the ground, then draining the underlying wetlands to make way for massive oil-palm plantations. As Greenpeace's banners made clear, that deforestation is destroying the habitat of the Sumatran tiger.

But truth be told, the animals are really beside the point. Greenpeace's tigers are a kind of decoy

"It's easy to say, 'If you're destroying forests, you're destroying tiger habitats,'" says Phil Radford, director of Greenpeace USA "It's harder to say, 'Do you know that forests store carbon and if we save the peat bogs we will trap all this carbon and methane in the soil?' We say both, but we start with the place that people are, the thing they care about the most first."

What seems to happen, inevitably, is the multinational company, eager to remove the stigma from its signature brand, promises to ensure that its products are sustainable and begins cancelling contracts with any third-party suppliers who fail to guarantee compliance.

Meanwhile, unlike several other environmental groups, including the World Wildlife Fund, the Sierra Club, the Environmental Defense Fund, the Audubon Society, Conservation International, and the Nature Conservancy, Greenpeace does not accept corporate or government funds. "We don't have anything for sale," says Rolf Skar, Greenpeace's forests campaign director. "What we learned from that is it was unrealistic to expect government to take the lead," Skar says. "In order for government to reform land use, generally they need some sort of consensus.

Giving Up On Government

Greenpeace's energetic crusade to turn corporate transgressors into eco-champions came about in response to a sudden realization that the traditional approach, pushing for government regulation, had become a spectacular failure.

"A lot of NGOs working on deforestation had a bit of a pipe dream that some sort of U.N. climate treaty or U.S. law, cap and trade or something, would save the day," says Rolf Skar. "The disappointment that was Copenhagen" — the 2009 U.N. climate summit widely regarded as a bust — "left a lot of us scratching our heads about what to we could go next."

In many of the key countries where Greenpeace operates, authoritarian regimes and rampant corruption can create further difficulties.

"What we've come to learn from Indonesia and other countries that are incredibly corrupt, is if you can flip enough companies, then civil societies and the companies together can get laws passed," Radford says.

Dealing with multinational corporations is a walk in the park. "Companies tend not to show up with automatic rifles and start shooting inches above your head," Skar observers, referring to the aggressive tactics employed by the Russian military in the arctic standoff.

They also worked to address the problem in your question about CFCs.

A Greenpeace staffer in Germany had worked with a scientist to pioneer a clean new refrigeration technology, dubbed Greenfreeze, which had since been widely adopted throughout Europe and Asia, resulting in a massive decline in the release of hydrofluorocarbons.

For an example with water and rivers (not air), Markets Not Capitalism, pg. 415 (PDF pg. 427)

The Clean Water Act versus Clean Water

For a perfect illustration of how legislative environmentalism is actively hurting environmental action,
check out this short item in the Dispatches section of the May 2010 Atlantic.
The story is about toxic mine runoff in Colorado, and describes how
statist anti-pollution laws are stopping small, local environmental groups
from actually taking direct, simple steps toward containing the lethal pollution
that is constantly running into their communities’ rivers. Also, how
big national environmental groups are lobbying hard to make sure that the
smaller, grassroots environmental groups keep getting blocked by the Feds.

Near Silverton, the problem became bad enough to galvanize
landowners, miners, environmentalists, and local officials into
a volunteer effort to address the drainage… With a few relatively
simple and inexpensive fixes, such as concrete plugs for
mine portals and artificial wetlands that absorb mine waste,
the Silverton volunteers say they could further reduce the
amount of acid mine drainage flowing into local rivers. “In
some cases, it would be simple enough just to go up there with
a shovel and redirect the water,” says William Simon, a former
Berkeley ecology professor who has spent much of the past 15
years leading cleanup projects.
But as these volunteers prepare to tackle the main source of
the pollution, the mines themselves, they face an unexpected
obstacle – the Clean Water Act. Under federal law, anyone
wanting to clean up water flowing from a hard rock mine
must bring it up to the act’s stringent water-quality standards
and take responsibility for containing the pollution – forever.
Would-be do-gooders become the legal “operators” of abandoned
mines like those near Silverton, and therefore liable for
their condition.2

Under anything resembling principles of justice, people ought to be held
responsible for the damage they cause, not for the problems that remain after
they try to repair damage caused by somebody else, now long gone.