Using drush to sql-sync local to remote, without remote MySQL binaries on remote
Drush version 3 and onward (via the sql-sync command) can only copy the database via the ssh + mysql executable method that you describe above.  If you download drush 2.1 (https://drupal.org/node/614830), you will find a command drush sql-load that works as you describe.  It's a lot slower than sql-sync, so if your database is very large, you might find this technique to be too cumbersome.  If it works for you, though, it probably wouldn't be very hard to make your own external Drush commandfile to provide sql-load on a more recent version of Drush.