they could make steel cages, fill them with crushed and vibrated limestone (or another aggregate). Good steel for the cage would last a lifetime but not sure if it's cheaper in $$ or CO2 emissions. Basically they need to lift /drop a heavy thing that last generations and stacks well.

Concrete has the advantage of lasting "forever" in those conditions (rebar when wet ruins it, otherwise it last long, long time). Concrete also stacks perfectly as you can mold it however you want. Might bite the bullet and stick with concrete, just work on making it more efficient.

yep, hence the use of waste material wherever possible.

Not a true expert on the topic but from my reading it sounds like land is generally a carbon sink and water produces carbon so when you turn land into water, the net effect is additional carbon. Estimates have man-made reservoirs accounting for 0.5% of the total anthropogenic carbon emissions worldwide; fairly significant when we're considering the scale needed for energy storage with wind (blows 35% of the time, US avg.) and solar (shines 25% of the time, US avg.).

http://documents.worldbank.org/curated/en/739881515751628436...

It's carbon neutral when plants decay to carbon dioxide. But they need oxygen for this to happen - and when they don't (like when they're underwater), they decay to methane.

And methane is a greenhouse gas 20-80x more potent than carbon dioxide.