Motivated by gravitational wave observations of binary black hole mergers, we present a procedure to compute the leading order nonlinear gravitational wave interactions around a Kerr black hole. We describe the formalism used to derive the equations for second order perturbations. We develop a procedure that allows us to reconstruct the first order metric perturbation solely from knowledge of the solution to the first order Teukolsky equation, without the need of Hertz potentials. Finally, we illustrate this metric reconstruction procedure in the asymptotic limit for the first order quasi-normal modes of Kerr. In a companion paper, we present a numerical implementation of these ideas.