Duke Nukem had some 2.5 D stuff going on that was more powerful than what doom was doing, but just barely. I think the first fully 3d game that meets your definition is probably 'Descent'