Well nowadays you can probably just use OpenGL. In fact there are many OpenGL powered source ports of games like Doom, Duke Nukem, etc... They don't have to rely on any tricks for rendering geometry. They just render a bunch of arbitrary polygons and don't even think about perspective or anything. Just set up the camera correctly, etc...
Since you have the zbuffer, you don't need to worry as much about rendering polygons in the correct order. Overdraw isn't too much of a problem either, games overdraw nowadays all the time just fine. There are ways to prevent it a bit, by roughly rendering polygons front to back. That requires some sorting though. Some engines do a depth prepass by rendering the geometry only to the depth buffer with color write off, making the pixel shaders do no complex work. Then rerender the scene again, and this time there's no pixel shader overdraw on solid geometry.
You can still have sprite based FPSes, just draw a flat billboarded rectangle with the sprite instead of a model. In fact there's even a killing floor mod with doom enemies. https://www.youtube.com/watch?v=X2O7nmuvwDo&noredirect=1
Doom did some things, such as making all walls at 90 degree angles with slightly brighter or darker lighting to add contrast. Also the diminished distance lighting, making things darker farther away. Now that's just done with fog.