I know you can do useful things with Exceptions when necessary. However I have to say unequivocably that using an exception in this case would be the worst possible idea. Why? Because the exception would be NoMethodError (ie. from nil[:key]). This equivalent to a NullException in Java, indicating all manner of generic logic errors that could have occurred anywhere within the stack.
If you looked at what I was actually doing, you might agree that SafeNestedHash is an incredibly useful abstraction. Hell, if it was written in PHP you could look at the algorithm and say, "wow, that's fast, elegant and readable." I'm not sure why you're so dead set that I'm doing something wrong, but you're just pulling this stuff out of thin air without any context.