This should probably be a comment, but it's too long so I am posting it as an answer.
I'm not sure I necessarily agree with "[A Pigouvian tax] is a fixed unit price, which cannot be efficient if the damage costs are highly non-linear." But I do definitely agree with the fact that non-linearity causes practical problems for a Pigovian implementation, as I note below.
Suppose that the private benefit from emissions is $\pi(e)$, and that emissions cause external damages of $d(e)$. Assume that more emissions lead to greater damage ($d'(e)>0$), that the marginal damages are increasing ($d''(e)>0$—so damages are non-linear), and that profits are concave ($\pi''(e)\leq0$).
The self-interested individual will maximise his payoff by solving $\pi'(e)=0$. In contrast, social welfare is maximised when $\pi'(e)-d'(e)=0$. As usual, there is an inefficiently high level of emissions.
Write $e^*$ for the level of emissions that is socially optimal, and suppose that we set a Pigouvian tax at $t=d'(e^*)$ per unit. This means that the individual's optimisation problem is now
$$\max_e \pi(e)-te=\max_e \pi(e)-d'(e^*)e.$$
The corresponding first-order condition is
$$\pi'(e)-d'(e^*)=0.$$
This is solved by $e=e^*$, so the private individual is therefore induced to choose the efficient level of emissions even though the external damages are non-linear. Intuitively, if decisions are made at the margin then all the Pigouvian tax needs to do is to ensure that the private marginal benefit is equal to zero exactly when the social marginal benefit it. That the tax does not equal the external cost for all of the infra-marginal units has no bearing on the marginal decision problem.
Although the Pigouvian tax implements the efficient level of emissions, its implementation has important normative consequences. In particular, the polluting individual is paying a tax of $d'(e^*)$ for every unit of emission, even though the marginal external cost of the first $e^*$ units is less than this (because $d$ is convex). This implies that the polluter is required to pay more than the cost that he imposes on society, which some might not consider equitable.
There is also an awkward inter-temporal dimension to this problem that is not considered in the above static "textbook" treatment. Because damages are non-linear, if I allow $e$ units of pollution "today" then the marginal cost (and hence the optimal level) of emissions "tomorrow" will be different to if I had allowed $e+1$ units today. This seems to suggest that what is really needed (if the solution is, indeed, to be Pigouvian) is a time-varying tax and the problem becomes one of optimal control. That is, rather than calculating a single tax rate, we need to find the time-path $\{e_t^*\}_{t=0}^{\infty}$ that characterises the optimal evolution of emissions and change the tax over time to implement this. This increases the burden on the central authority, which is now required to calculate not only the emissions it wants to allow today, but also the emissions that it anticipates allowing into the indefinite future. This makes the informational problems noted in the question significantly more acute.