Let me just start with saying that the results on the stability of black holes are not complete yet. The question is whether 1) a black hole is stable with respect to linear perturbations, and 2) whether a black hole is stable to finite (non-linear) perturbations. I am just going to tell you that 2) has very few results concerning mainly the Schwarzschild background and special perturbations (you can also "cheat" by making your background de-Sitter, see Hitz & Vasy, 2016), and it will probably still take a while to obtain a more complete picture (it took decades to prove non-linear stability of even something as simple as the Minkowski background).
However, the answer to question 1) is yes for subextremal black holes, and in the exterior and on the horizon (things get funny at Cauchy horizons and curvature singularities). This is known analytically for Kerr black holes (Whiting 1989) and Reissner-Nordström black holes (Moncrief 1974), this naturally includes the Schwarzschild limit (this special case was investigated way back by Regge & Wheeler 1957). A special case is Kerr-Newman, where perturbations do not have separable equations and the results are thus only numerical (but affirmative, Dias et al. 2015). The method used to show this is mode stability, that is, decomposing the perturbation into (tensorial) spherical harmonics and finding frequency eigenmodes. Every frequency eigenmode generally has a real and an imaginary part, corresponding to the oscillation of the mode and exponential decay/growth. One then shows that physical modes can only decay (physicality is expressed in boundary conditions). A physical perturbation decomposed into eigemodes must thus decay as well.
A lot of concern is also spent on which perturbations and with which properties have convergent decompositions into such modes. Ultimately, many people ditch mode stability but rather analyse the general initial value problem by various quantitative bounds and estimates. This approach unambiguously resolves various issues connected to the global structure of the space-time (throat, white hole, black hole,Cauchy horizon,...), but to me as a physicist seeing the exact black hole space-times only as local-in-space-time approximations of the field, mode stability would be sufficient. So far, this program was finished only for the simpler case of a scalar wave equation on the black hole background (Dafermos et al., 2014).
The perturbations fulfill wave equations on the background and these will have an action formulation which itself can be viewed as a an expansion of the full action in functional space to second order in the perturbations (the linear order term vanishes because the background is a solution of $\delta S = 0$). A variation of this linearized action is proportional to a second functional derivative of the original one times the perturbation and the vanishing of the variation can be written as "$ h \cdot \delta^2\! S/\delta h^2 = 0$". So the solutions correspond to zero-eigenvectors of the Hessian of the action. The fact that this equation is fulfilled while a physical solution is unbounded would require that there are singularities and/or degeneracies in the Hessian as well. I do not know how that relates to your statements about the Hessian in the OP.
Ultimately, I believe having a negative spectrum in the Hessian would not indicate a classical instability, but rather a quantum one, as a semi-classical expansion of the path integral would suggest. In other words, the black hole state would tunnel into another state that would possibly not be reachable by a classical process. I am not aware of an analysis of this type for black holes, and it is not clear to me how should the end state of the tunneling look like.
