hi, shell_exec shouldnt require shell access but the new host may disable it or you dont have proper permissions. also its possible that they dont have gd installed.
one way to test if shell_exec works is just do this in an indiviual script:
$res = shell_exec("echo hi");
echo $res;
if you get 'hi' displayed in the browser shell_exec works and they dont have imagemagick installed, otherwise you cant use shell_exec. you may then try exec.
also make a script and in it put only
<?php phpinfo(); ?>
this will display the properties of php. there you can see if gd is installed and configured. if its not, then you are out of luck.
also. if shell_exec works, try shell_exec("whereis imagemagick");
shell_exec("whereis mogrify");
to see if they are installed.