Can I run Drush in a situation where the database is on one server and the remainder of the Drupal installation is on another?
I've never run a Drupal site like this, but Drush should take your database settings from your settings.php file; if the database is remote for Drupal, then it should be remote for Drush as well.  Note that most Drush commands (with the notable exception of the sql-* commands, which you will not be able to use without a local mysql installation) just call through to the corresponding Drupal code, after first bootstrapping.  If your bootstrapping is failing, check to see if there is anything in your settings.php that depends on the site's URI to select the database.  If so, make sure that you use the --uri= flag, or set the 'uri' element in your Drush site alias when using Drush.  If that doesn't get you going, post the output of a failing Drush command with the --debug flag specified.