This paper proposes and analyzes a mixed variational formulation for the Navier-Stokes equations with variable viscosity that depends nonlinearly on the velocity gradient. Differently from previous works in which augmented terms are added to the formulation, here we employ a technique that had been previously applied to the stationary Boussinesq problem and the Navier-Stokes equations with constant viscosity. Firstly, a modified pseudostress tensor is introduced involving the diffusive and convective terms and the pressure. Secondly, by using the incompressibility condition, the pressure is eliminated, and the gradient of velocity is incorporated as an auxiliary unknown to handle the aforementioned nonlinearity. As a consequence, a Banach spaces-based formulation is obtained, which can be written as a perturbed twofold saddle point operator equation. We address the continuous and discrete solvabilities of this problem by linearizing the perturbation and employing a fixed-point approach along with a particular case of a known abstract theory. Given an integer l >= 0, feasible choices of finite element subspaces include discontinuous piecewise polynomials of degree <= l for each entry of the velocity gradient, Raviart-Thomas spaces of order l for the pseudostress, and discontinuous piecewise polynomials of degree <= l for the velocity as well. Finally, optimal a priori error estimates are derived, and several numerical results confirming in general the theoretical rates of convergence, and illustrating the good performance of the scheme, are reported.