We present a 7 yr timing study of the 2.5 ms X-ray pulsar SAX J1808.4-3658, an X-ray transient with a recurrence time of ~2 yr, using data from the Rossi X-ray Timing Explorer covering 4 transient outbursts (1998-2005). We verify that the 401 Hz pulsation traces the spin frequency fundamental and not a harmonic. Substantial pulse shape variability, both stochastic and systematic, was observed during each outburst. Analysis of the systematic pulse shape changes suggests that, as an outburst dims, the X-ray hot spot on the pulsar surface drifts longitudinally and a second hot spot may appear. The overall pulse shape variability limits the ability to measure spin frequency evolution within a given X-ray outburst (and calls previous nudot measurements of this source into question), with typical upper limits of |nudot| < 2.5x10^{-14} Hz/s (2 sigma). However, combining data from all the outbursts shows with high (6 sigma) significance that the pulsar is undergoing long-term spin down at a rate nudot = (-5.6+/-2.0)x10^{-16} Hz/s, with most of the spin evolution occurring during X-ray quiescence. We discuss the possible contributions of magnetic propeller torques, magnetic dipole radiation, and gravitational radiation to the measured spin down, setting an upper limit of B < 1.5x10^8 G for the pulsars surface dipole magnetic field and and Q/I < 5x10^{-9} for the fractional mass quadrupole moment. We also measured an orbital period derivative of Pdot = (3.5+/-0.2)x10^{-12} s/s. This surprising large Pdot is reminiscent of the large and quasi-cyclic orbital period variation observed in the so-called black widow millisecond radio pulsars, supporting speculation that SAX J1808.4-3658 may turn on as a radio pulsar during quiescence. In an appendix we derive an improved (0.15 arcsec) source position from optical data.