Do my specific constraints prevent me from using this Zero and Span Amplifier?
I suggest that you flip over the voltage divider so that you get a range of 0.2V to 3.3V. 
It's generally better to have one side of the sensor grounded anyhow. 

Then you can work out the resistors to get 0~4V for 0.2V to 3.3V. 

Another suggestion might be to just connect the op-amp as a unity-gain buffer, and reduce the 82K to 40K so you get 4V at 32°F and 0.348V at 212°F. That gives you an offset zero so you don't suddenly run out of range close to zero C (depending on op-amp offset) and you still get 91% of the resolution. 

Speaking of resolution, note that the resolution at high temperature will be much less than the resolution near 32°F, so you should make sure it's good enough for your purposes. It's important to take the op-amp offset into account too, since it greatly affects the high temperature measurement (and the low temperature measurement hardly at all). If one particular temperature is of the most interest, a strategy is to use that value of resistor as the other half of the divider (and use ratiometric conversion) because that's where the resolution will be maximum. 

Ratiometric is usually the way to go with resistance measurements because the reference voltage has no effect on the measurement, all that matters is the reference resistor value. 

If you do a sensitivity analysis on the method you originally suggested, I think you'll find it adds a lot of error unnecessarily. 

To answer your specific title question, yes you can't do this without a voltage higher than 5V to offset the output that much. That's a consequence of the low gain (about 1.3) and the large offset.