Fast approximation of spherical texture coordinates
Incidentally I implemented something similar for similar hardware some 20 years ago (:

IIRC, I calculated 1D look-up-table using acos for parallel projection of a cylinder and just scaled it for each scanline to reduce computation cost. The LUT just gives you x-coordinate offset to the texture and you add constant offset for each scanline for the rotation.

For y-axis the input texture can be preprocessed to have proper spherical distortion applied and you can just linearly scale the texture vertically. Though it's not that much extra computation to do it run-time either.

This doesn't give you proper perspective projection but might be enough for your purposes.

Edit: Didn't notice you said you can't afford LUT. You could do the table look-up every N pixels and linearly interpolate inbetween. This was a common method in the past to do affordable perspective correct texture mapping for software rasterizers to avoid div/pixel