If your host don't have shell access, you should look for a new host... They all claim it's for security, but if they do an efficient job of security in the first place this shouldn't even be an issue.
As for what to do, you could TRY using the GZip compression option with PHPMyAdmin, or using a program such as SQLYog which has a virtual tunneling script that it uses to interface with ones server (though it's pretty slow and it's not free).
Some control panels allow you to make backups from the control panel itself; where this option isn't ideal, it makes a server side copy of data from the server, so all data should generally be in tact.
Regardless, always make sure your backup is complete!
