Do you have command line access? If so you can use the mysql command line tools ( see mysql.com for docs on mysqldump ).
If not, you will need to write a script to do the work. Which is exactly what phpmyadmin is, just a php script. A set of scripts, actually. As long as you don't hard code the username and password into the phpmyadmin config I don't see what the harm is.
Lacking any of that I guess you would have to ask your current host to make a database dump for you.