The best way is to get command line access to your server. This is usually done using telnet or ssh. Sometimes in your hosting cPanel you might have an option to open an SSH connection or Secure Shell connection, or similar?
If it's a VPS rather than a shared server then you might have something like kvm access to control it directly.
Your hosts might be able to give you more specific information.
PHP My Admin doesn't do a great job with backing up databases either unfortunately.
That's mainly due to the SQL file a (large) text file, in which are simply commands MySQL uses to restore data back to the database. If you open the file in a text editor, look at the end of the file and you should see something similar to:
Be aware you may not be able to restore your database the same way.
One piece of advice, check your backup. I routinely backed up my database only to find that it wasn't backing up all the tables.
Generally, yes. Note this is only for SQL; you'll still need to back up the actual files on the server separately if you want a full backup. If there's little change in the files depending on how often you backup, it's not usually necessary to copy the files every time you do database backups.
My database is about 700MB or so, but when I export it fully compressed it comes out to be around 100MB. I can then completely restore it without problems, so the size might not be the problem.