exec
is almost always turned off by shared hosts because it represents a security risk to both you and them. It allows you to use PHP to run shell commands, which in turn lets people take control of your server. They won't advertise a security risk.
What you want is a virtual private server (VPS, sometimes called a "cloud" server). A VPS lets you set the environment directly, without affecting other users because your machine looks like it is separate but it's really sharing resources. You can check out 1and1, Amazon Web Services, etc if you want to get one and they are roughly comparable to most shared hosting packages. The catch is you need to set it up. I would further suggest you use a control panel like Plesk or cpanel to help you if you don't know how to administrate a Linux box.