Emitting fossil fuels is generally recognized to cause a net external cost, a large part of which occurs in the future. In a perfect world the costs and benefits of greenhouse gas emissions could be objectively determinable at no cost with great accuracy and precision; money would then change hands to account for these costs and benefits in order to cancel them out.
The real world is not at all like that. As best we are able to determine it appears that adaption is misery and triage and it will be a great; some countries will benefit, but most won't and its expected to be a great net cost to the world. Many of the costs are subjective; what's the cost of the loss of some species? If the maldives shrink and eventually disappear, there's an objective cost of moving people around, but there's also a subjective cost to the inhabitants.
The purpose of a greenhouse gas tax is to do a half-assed job of internalizing future external costs into the current price of a good or service, under the theory that doing a half-assed job is better than doing none at all.
Fossil fuels, meat production and biofuels are provided with quite enormous subsidies in many places; before bothering to do something rather more difficult, stop that. This is an easy to rectify harm.
Whether government needs to be bigger or smaller is an issue entirely separate from GHG taxes. In order to offset the additional taxes collected on GHGs it would be necessary to ramp down VAT, sales tax, employment taxes, income tax or other taxes to cancel it out. If you don't do this the battle becomes over whether government should grow or shrink rather than whether GHGs should be taxed or not.
It does not make sense to only tax carbon dioxide and not the other major greenhouse gases. On the one hand you want to be fair and not give an undue advantage to some technology like biofuels(N2O) or natural gas(if ~2-3% of natural gas leaks out it is no better than coal over the next 100 year period); on the other hand you don't want the unnescessary complexity of worrying about unimportant greenhouse gases.
The cost of regulation should be insignificant compared to the tax collected; otherwise you are introducing a huge dead-weight loss.
If you introduced a tax only on domestic GHG emissions, this would give domestic companies a competitive disadvantage compared to foreign companies not burdened by such a tax. You make a lot of politically powerful enemies this way. This isn't likely to ever be implemented anywhere.
If you try to establish some type of world government body that applies a uniform tax on GHG everywhere you would solve this problem but you would create several problems which are even harder to solve. This extraordinary degree of political cooperation would be hugely unpopular, incredibly difficult to achieve, it would undermine national sovereignty, the political body that administers it would be remote and unaccountable. You're opening yourself up to all kinds of mischief. It may be used as a political club by the powerful nations to beat up the less powerful ones. It may, as in the case of the EU, suffer from galloping mission creep. The EU was was sold as a free-trade and currency union; the currency union was designed to fail, forcing a crisis that can be used as a stepping stone towards a political union. Unwanted by almost everyone, it is fast becomming a united states of Europe. World government is a plain awful idea on every level and neither can, will or should happen. Trying to create world government will waste a lot of time and effort; it will give the paranoiacs who believe GHGs to be some kind of socialist or government conspiracy a huge shot in the arm.
From the above, the solution I would like to see is a GHG tax that is not applied to any exports; nor is it applied at any stage in the production. My GHG tax would be applied as a sales tax, at the point of consumption for finished consumer goods and services. This would replace the arbitrary sales tax we have today and would possibly have to eat into VAT and other taxes to remain revenue neutral.
This has several advantages. It does not disadvantage domestic producers; you don't piss them off so much as to create new political enemies. Implemented properly, if two regions adopt this policy it should not cause double taxation or loop holes that allow evasion of the taxation on goods that flow between them; the tax occurs only at the end point.
The beauty of this is that you can adopt such a carbon tax unilaterally; you can have different rates in different countries without introducing too many new opportunities for arbitrage(the only one I can think of is end consumers who live near a border to a low carbon tax country, who may choose to cross that border to buy a particularly carbon intensive item).
As usual, the devil is in the details. You don't want undue invasion of privacy and obstruction of business activity. For business who refuse to properly account for GHGs or cannot account for the GHG emissions of an imported good, you can give the option of simply assume the worst-in-class GHG emissions for the offending item. It must be worst-in-class, otherwise businesses would choose not to disclose GHG emissions whenever they exceed the standard rate. This is simplification and cost-reduction measure; for low volume production boutique items and minor ingredients the worst-in-class GHG tax would be much smaller than the cost of figuring out the actual GHG emissions when not explicitly given by the manufacturer.
There are some ugly corner cases that would need to be sorted out. E.g. grocery stores take in more perishable goods than they need because it costs them more to leave a customer's needs unfulfilled than it does to throw away significant volumes of expired goods.
It's clear that it would be a significant expense to switch over; but the switch is a one-time cost and it is not unprecedented(e.g. the introduction of VAT or sales tax were also expensive one-time costs).