The S stars orbiting the Galactic center black hole reach speeds of up to a few percent the speed of light during pericenter passage. This makes, for example, S2 at pericenter much more relativistic than known binary pulsars and opens up new possibilities for testing general relativity. This paper develops a technique for fitting nearly Keplerian orbits with perturbations from the Schwarzschild curvature, frame dragging, and the black hole spin-induced quadrupole moment, to redshift measurements distributed along the orbit but concentrated around pericenter. Both orbital and light-path effects are taken into account. It turns out that absolute calibration of rest-frame frequency is not required. Hence, if pulsars on orbits similar to the S stars are discovered, the technique described here can be applied without change, allowing the much greater accuracies of pulsar timing to be taken advantage of. For example, pulse timing of 3 μs over 1 hr amounts to an effective redshift precision of 30 cm s-1, enough to measure frame dragging and the quadrupole moment from an S2-like orbit, provided problems like the Newtonian "foreground" due to other masses can be overcome. On the other hand, if stars with orbital periods of order of a month are discovered, the same could be accomplished with stellar spectroscopy from the European Extremely Large Telescope at the level of 1 km s-1.