We have recently introduced a class of non-quadratic Hessian-based regularizers as a higher-order extension of the total variation (TV) functional. These regularizers retain some of the most favorable properties of TV while they can effectively deal with the staircase effect that is commonly met in TV-based reconstructions. In this work we propose a novel gradient-based algorithm for the efficient minimization of these functionals under convex constraints. Furthermore, we validate the overall proposed regularization framework for the problem of image deblurring under additive Gaussian noise.