I'm running a software, where clients connect to my db via port 3306. I can't use regular shared hosting, as there I need to request for each client's IP to be added to the firewall, which is a pain in the butt and some clients may want to connect from different IPs or have dynamic IP, so I can't use it like that. And I don't want to pay for VPS or dedicated either, if I don't have to. Is there some solution? Some hosts which allow this?
You could sign up at Amazon AWS and get 1 year of free use for a RDS (mysqld) instance. They allow creating wildcard entries in their security groups - we have some dev and testing instances running at our company and remote connections work fine - but performance is subpar of course due to the nature of the mysql server - client protocol. Make sure to download the server certificate have your clients connect over SSL.
you can do it from cpanel as well in shared hosting, there is an option of remote access add % sign there. google it. or try to look for an affordable vps.