Concrete is the cheapest option, but getting fine detail is a problem (it can be done, but it is difficult and may compromise structural integrity), as are weight issues. I disagree with your assertion that expanding foam needs to be sealed as thoroughly; coating the foam is an aesthetic, not a water quality, issue, and missing a spot will have zero effect on your fish. I also disagree with your implication that tools and techniques for casting epoxies are not well-developed; this is simply not the case, and a great deal of info is available online.
I'd tend to guess that sealing requirements are roughly equal. I've done a fair bit with "Great Stuff" and other brands of expanding spray foam. The skin it forms when allowed to cure in contact with air seems solid, but if you needed to shape it all you expose the foam interior. You might not *need* to seal that, but I think you'd want to. You'd certainly want to seal concrete, but if you missed a few small spots I doubt the amount of leaching would be a problem as long as you do regular water changes and such.
I also disagree with your implication that tools and techniques for casting epoxies are not well-developed; this is simply not the case, and a great deal of info is available online.
Oops, didn't mean to imply that. Yeah, casting epoxy is well-documented and not too hard (that's actually what most rock-climbing holds are), but cost is prohibitive if you were trying to do a large aquarium background. Plus, you've got nasty fumes and such to deal with. I may be wrong, but I feel like concrete would be simpler, even if you couldn't get the same level of detail. I'm not so worried about losing fine detail, though.
A two-part expanding urethane foam mixture is used by taxidermists to cast mannikins, bases, etc.; it is non-toxic and should be ideal in the aquarium. The only trouble is its cost and its light weight (it would need some sort of weight in the base if not directly attached to aquarium structure).
Good suggestion, Newt. Same stuff is used by boat builders and others. Advantage over spray foam would be that you can pour it into a mold and have it fill voids better than spray foam, I'd guess. I'd expect you could pretty easily do some rough estimates of displaced water volume/weight and embed enough rocks in the lower portion of the wall to get negative buoyancy. I like the idea of being able to embed real rocks (as you could with concrete), but not wind up with a 300lb hunk of wall.

I might try this approach this summer.