  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
pulsar's 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.
