I've thought about this before, and I think there is some way you could find to do it. For example, you could generate on the mercator projection of the world, and then un-project. But the mercator distorts horizontal length approaching the poles. I think it would be complex to implement, but you could use larger windows closer to the poles to negate this.
You're still going to run into problems with mercator because under mercator the poles project to infinity, so you'd need an infinitely large texture or you special-case the poles. Many renderers do this so it is viable!
There isn't a zero tradeoff 2D solution, it's all just variations on the "squaring the circle" problem. An octahedral projection would be a lot better as there are no singularities and no infinities, but you still have non linear distortion. Real-time rendering with such a height map would still be a challenge as an octahedral projection relies on texture sampler wrapping modes, however for any real world dataset you can't make a hardware texture big enough (even virtual) to sample from. You'd have to do software texture sampling.
