If a constructor can fail, don't make that constructor public. Instead, add a trivial constructor to allocate an empty instance of the object, then make your possibly-failing constructor a factory function that takes whatever arguments you would pass to the constructor and returns an error code. The object being "constructed" should then be passed by reference as one of the arguments to the factory function and filled in. (If you're writing this in Rust, you have better options, since you can explicitly take ownership of some of the factory function arguments and avoid the need to allocate a trivial instance of the object by returning it as one of the variants of the sum type Result<T, E>.)
Note: I don't actually know C++ very well. It's possible there's a more idiomatic way to accomplish this. In particular, another wrapper class could be created that owns an instance of the trivially-constructed instance mentioned above. The factory function could then take an instance of the wrapper class and then modify and return an instance of the class you actually want to obtain.
You can't really tell if the stack overflowed in a constructor though, plus that will essentially /never/ happen, so I think it's okay to exclude stack overflows when creating stack allocated objects as failure conditions. In that case no, a lot of constructors won't be able to fail.
Any function can overflow the stack. If the object is constructed on the heap, 'new' can fail but will always throw an exception; if you aren't using exceptions it will just crash the process.
This is not an error that you can reasonably recover from. If you are out of stack, even constructing an exception to throw is likely to fail.
Because the only correct behavior here is to terminate the program immediately, it doesn't matter in the discussion of whether to use exceptions or not.
new can and does fail when you're out of memory, and this is a condition that many programs do need to handle (for some programs crashing is appropriate and in that case sure, you can live without exceptions). In a pedantic technical sense that's not the constructor failing, but your options for handling it are much the same.
std::optional is now confirmed for C++17, which can make the API a bit nicer. Using factory functions as pseudo-constructors also lets you name them, which is often nicer than having to rely on argument types to disambiguate constructors with different purposes.
Init methods is the answer to that (but it potentially forces some additional complexity around initialized/not-initialized state into the other methods).
As I stated in my original post, these have the same classes of problems as null pointers: you have "constructed" an object whose internal state in invalid; a instance of Foo is either a Foo that init'd successfully or not-a-Foo (that failed to init/isn't initialized; a "zombie object") just as a pointer is either a pointer-to-something or a pointer-to-nothing. This is why you say "it potentially forces some additional complexity around initialized/not-initialized state into the other methods.
At least in C++ (and many other OO languages), I find the downsides of having these Jekyll and Hyde classes outweigh any benefits that may come of ignoring exceptions.
In fact, I think managing this extra state, also dealing with complications that could arise from object slicing, were the major reasons given when Martin Sústrik argued he should have originally started out with ZeroMQ in C and not in C++.
How so? RAII works just fine when you return errors.