Your best bet is probably to go for magma, actually. There are a few ways to build underwater.
The first involves your plan, except reversed; you pump out the area, then build walls downward (while continuing to pump out the area, as the water will naturally attempt to flood the inexplicable hole in its surface). This method causes significant lag, takes a lot of resources to build all the pumps and their power system, and is very irritating since even with a solid ring of pumps there will still be occasional splashes of water on your walls' build locations, which causes them to be suspended.
The second involves dropping magma into the water to turn it into obsidian. You can either do a ring, or a solid block. If you do a ring, you can then pump out the center, but a solid block is nice since you then don't have to "build" underwater but can just mine it out. Much quicker, and then you can smooth and engrave everything. This method is significantly easier than the first, but of course takes access to magma. If you're building a pump stack to bring magma up, see my signature; the standard pump stack design causes massive lag if used on magma, while the designs discussed in the thread linked there cause much less.
The third method involves digging beneath the water, digging a ring around beneath where you want your ultimate underwater structure to be, linking that ring to a lot of drainage, making some way of blocking off those drains, then opening the whole ring to the water (such as through a cave-in from above to take out the floors separating the body of water from the drainage tunnels). Water flows down into that ring, drying out the build site, allowing you to build your structure, and, when you're done, you close the drains and let the water refill. Note that this method can also cause a lot of lag.