Well, we've already seen what can be done insofar as optimisations are concerned - specifically, I'm thinking with Castaway, where the original ST emus ported already (and optimised apparrently - pfff) were designed for 200 MHz Arm processors, and Skeezix managed to get it down extremely well to 133MHz...
So I'm guessing it would be possible... especially since the original quake ran on pretty low-end machines (486dx 66 wasn't it? Someone who's still got the min specs for original, please tell). Albeit, those were machine with FPUs, but if its already had a fixed point conversion...