Do you define bullet time as slow motion bullet dodging, or the spinny effect from multiple cameras in an arc?
There's a slow motion scene in the first Blade film where you can see the bullets moving through the air, giving the target enough time to reacting and move out of way. Blade came out in 1998, a year before The Matrix.
It's in the scene in Chinatown where Deacon Frost has captured a little girl, at around 2m45 in this YouTube clip (sorry it's in 4:3 squashovision).
The slow-spinny effect can be found in Lost in Space (also 1998) when they go into hyperdrive (around 1m20s in this clip).
Not a movie, but a similar spinny effect to The Matrix's bullet time can be seen in Michel Gondry's music video for The Rolling Stones' Like a Rolling Stone.
Also of note (but not a mass-movie), The Campanile Movie:
"a short film directed by Paul Debevec made in the spring of 1997 that used image-based modeling and rendering techniques from his Ph.D. thesis to create photorealistic virtual cinematography of the UC Berkeley campus."
"When I saw Debevec's movie, I knew that was the path."
-- Visual Effects Supervisor John Gaeta, WIRED 11.05.
Campanile project Master's student George Borshukov was hired by Manex Entertainment where he and his colleagues applied the Campanile Movie's virtual cinematography techniques to create some of the most memorable shots in the 1999 movie The Matrix.
The linked Wired article about The Matrix refers to both of these:
Fast-forward to the early 1990s, when another Frenchman, Arnauld Lamorlette, the R&D director for design firm BUF Compagnie, faced a problem similar to Laussedat's. Industrial clients examining buildings for structural flaws needed to see Paris from above. Parisian airspace, however, is tightly controlled; nonmilitary aircraft may fly over the city only on Bastille Day. Lamorlette found that by morphing between two photographs, he could generate a 3-D model: digital photogrammetry. BUF employed the technique to help director Michel Gondry create a music video for the Rolling Stones. Its radical camera moves - zipping through a room full of partygoers frozen in midmotion - caused a sensation in Europe. (BUF also used this method to make a Gap ad called "Khakis Swing" that was most Americans' first glimpse of the effect.)
Gaeta and Kim Libreri pumped up this technique for The Matrix: By triggering a circular array of 122 still cameras in sequence, they were able to simulate the action of a variable-speed movie camera that tracked completely around its subject. Because the cameras located on one side of the array were visible to those on the other side, however, they also needed a way to computer-generate photo-realistic sets so they could paint the cameras out of the frame.
Gaeta found the answer in 1997, at the annual visual effects convention Siggraph, where he saw a short film by Paul Debevec, George Borshukov, and Yizhou Yu called The Campanile Movie. The film - a flyover of the UC Berkeley campus - was generated entirely from still photographs. Like the 19th-century cartographers, Debevec and his team derived the precise shapes and contours of the landscape by triangulating the visual information in still photographs. Then they generated 3-D models based on this geometry, but instead of applying computer-generated textures to the models, they wrapped them with photographs of the buildings themselves. The trick worked spectacularly well. Instead of resembling something out of Toy Story, the buildings and the surrounding hills in The Campanile Movie looked absolutely real.
And here's the 1998 Gap "Khaki Swing" advert.
