First why would you want to do this?
Php 4.X is being phased out and the latest that I think there is is 4.4.8
Mysql is also not going to support(no more patches or releases) the 4.X versioning.
The host you are considering is not staying current right now and I would be seeking one that at least has plans and stays current.
You should be positioning yourself now for Zen Cart 1.4

All this being said, Zen Cart 1.3.7 should have no issues with this step back.