I agree wholeheartedly regarding releasing carbon from the existing warehouses, those being primarily coal and oil deposits. But we can't refill those warehouses with any current technology.
We can build a bunch of USS Constitutions, though! (Hey, she's still afloat, which totally one-ups the HMS Victory).
As far as planting, there are very efficient ways to accomplish that. Which you choose depends on your purpose. I recently saw a technology which dropped seedling from an aircraft at relatively low altitude. Or you just use old farming technology. If you're planting seedlings, the energy cost is pretty low per tree. Even lower if you use seeds.
I've not heard the methane isssue before. I'll read up on it.