Wouldn't the most efficient way to mine such a coin be to be in an area with above average CO2 levels? Such as a closed room where you are burning oil/gas/wood? Have you heard of the cobra effect? See https://en.m.wikipedia.org/wiki/Perverse_incentive . Not saying what you suggest is impossible, but if it's possible to game the system I suspect it will be a net negative very quickly.
I think something like that would have to be manually audited by humans (i.e. you'd need to agree on a central authority who certifies volumes of carbon sequestered).
I was thinking the other day that maybe something that could be easier to objectively verify is something like a cryptocurrency where you generate a unit of currency when someone votes. Sort of like "I voted" stickers as a form of money. It's not a fully formed idea; I don't know how the logistics would work.
Bonus points if the currency as a whole is valued higher or lower based on individual voters rating their voting experience. Like, you ask them on a scale of 1 to 10 if they think they have a real voice in how their government is run. Thus countries would have an incentive to be democratic in a way that's truly responsive to the people and not just some kind of democracy theater.
Make a government buying carbon. Like one cubic meter is $1000 or whatever cost would be interesting. Spend the money and bury those cubes in deep shafts. Let the market handle it.