If you don't want to compute the Hessian, you're at the wrong address with Newton's method. Quasi-Newton methods is where you want to look.
Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.