Fatal Error After Updating WordPress – No Fixes Work!

I recently tried to update to the most recent version of wordpress. After the update, I got a screen saying:
“WordPress has been updated! Before we send you on your way, we have to update your database to the newest version.

The update process may take a little while, so please be patient.”

When I try to continue with upgrading the database, the following error occurs:
“Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 52 bytes) in /home/cityques/public_html/wp-includes/wp-db.php on line 1296”

I have searched through the forums and know that this is not an uncommon error. I have increased the memory limit in my PHP file to 256M, but I still get the error.

I have had my hosting providers try to fix the problem by increasing memory limits but they have had no luck either. In fact they broke part of my site and I have had to upload a backup of wordpress via filezilla to restore it to normal. I thought this would fix the problem by reverting to an older version of wordpress, but it is still happening.

I would like to disable my plugins, try updating and then reactivating, but I can’t access my WP-Admin site because of these messages. Is there another way to do it?

Is there another fix to this problem that I am not aware of? I am a novice code editor, but any help would be appreciated!!