Zen Cart uses CURL for most advanced communications.
It only relies on allow_url_fopen for a few things (and this will change in the next release):
- USPS quotes
- UPS-US quotes
- PayPal IPN confirmations
- Currency updates in the admin (but do a fallback to CURL anyway)
- Admin new-version alerter (which can be disabled)

Other addons may require it.

The Zen Cart installer does not use any fopen resources, so the allow_url_fopen issue you mention has no bearing on installer problems. The installer does attempt to test CURL though, but not until the System Inspection page.

You have a few options:
a) continue if you can live with the above limitations
b) use a (different) host which has been proven to work with Zen Cart because they value ecommerce customers
c) or, as you said, find something else