It's true that it can get tricky, but I'd be inclined to write a tricky implementation, instead of inconveniencing the client of the class.
I don't understand exactly what you example is, but I'm sure it could be resolved by some combination of nothrow new, a try catch function body, and separating out each discrete step into it's own try catch combo. If you explain it better, I'm sure I could provide a solution.