@Ronan ...
Not all hosting providers are as accomodating.
Sounds like your hosting provider does not configure DB's using InnoDB on your 'shared DB' server. If that is what they meant, ask if there is another DB server that has the InnoDB engine configured and allowed and if they do, move your DB's to there.
If they cannot do or won't do, seek another provider or explore options to move your purchased package upwards to some level where you can get supports needed for Moodle. Think gone is the day one can purchase the cheapest package and expect Moodle to run and/or expect Moodle can be upgraded.
You also might want to inform them that there are some command line scripts that they should be able to use (you probably do not have ssh access into a shared server) in moodlecode/admin/cli/.
'spirit of sharing', Ken