I'm not sure that a dedicated IP address will be of help for you.
I could be wrong, but the email server will probably continue to use the shared IP, even if you buy a dedicated IP.
You could avoid the issue only migrating to a dedicated server or VPS (at higher costs, of course). Probably only in this case your associated IP will be used by the SMTP server.
About using the google smtp, the access to third party SMTP servers could be blocked by your provider. If it's not, you could give a try to it.
But you have to inform your hosting provider's support about what's happening.
And since the issue could be solved only after weeks, I would ask your provider to be moved (at no cost) to a new shared server not affected by the blacklisting issue !
(of course I suppose you are not the cause of the blacklisting
)