alex121121

First, check the php version you are using in admin->tools->Server Info, It has to be 5.3 or above. If it is, edit the admin/auto_update_currencies.php file and change
if (! isset($_SERVER['HTTP_USER_AGENT'])) { //ran by cron require('includes/application_top.php'); } to
require('includes/application_top.php'); Does that make a difference?

The code compares the current hour to what you have in the setting. If you have it set to 10 and you never login to your admin before 10, the script will never run. Also, it only runs when you are on the index,php page of admin. So sometime before 10 go to ...com/admin/index.php and it should run.
You can run it manually by going to ...com/admin/auto_update_currencies.php If that works, then it is a time or page issue as described. If it doesn't, then it is probably due to the links for currencies. Try updating the currencies manually in the currencies section of admin to see if the code will do it.

If the code only looks at the time of day, and doesn't keep track of the day on which it was last run, it's not very good code. Anyway, if you can't run a proper "cron" job, look at "poor man's cron" examples that do track when the last time something was run was, and kick off the run if enough time has passed. Such code would be started from some place in osC such as application_top.php. I think there may be a poor man's cron in one of the mass mailing add-ons, where you don't want to dump an avalanche of emails on the system, but just dribble out a few at a time, then wait for the next run of osC that's a few minutes later. I don't know if anyone has generalized a PMC to run arbitrary modules at arbitrary times/dates, but that would be a great feature for osC.
Perhaps you would be better off if you worked with your host to understand what their limitations are on cron jobs. It's understandable that they want to keep out-of-control scripts off their servers, but cron is a necessary part of any non-trivial website. You got burned once by not understanding what they allowed, but that doesn't mean you can't craft a cron job that they will allow.

Does your host actually not let you run cron (on a Linux server), or do they restrict the kinds of things you can run, such as PHP scripts using 'php'? Mine does the latter, but they allow using cURL to run PHP scripts.

Step 3 is only for when cron won't work. If you use step 3, you have to apply the database change mentioned

If you did that and it didn't fail, the setting has to be in your database. I've seen some templates that sort the configuration settings into different sections so that there is more than one configuration section in admin. Short of something like that, I can't even guess at what went wrong. You can search the database for AUTO_UPDATE_CURRENCY_BEFORE, which that sql change adds. It has to be there somewhere if there were not any failures.