Is it possible to create some sort of addon whose data is stored on a different database?

Sure, I'm pretty sure this should work (based on the CodeIgniter docs):

$config = array(
    'hostname' => "localhost",
    'username' => "myusername",
    'password' => "mypassword",
    'database' => "mydatabase",
    'dbdriver' => "mysql",
    'char_set' => "utf8",
    'dbcollat' => "utf8_general_ci"
);    
$this->EE->custom_db = $this->EE->db->load->database($config);   
// Now use $this->EE->custom_db->query(), etc

Since this won't be using Channels, how would I make my back end interfaces appear in the Control Panel?

You'd have to build the interfaces yourself, using "view" files inside your add-on, which can then use EE's helper classes to build forms, tables, etc for display. (See the module tutorial for some guidance.)

Will I be able to loop through the entries like I do with Channel entries (using tag pairs)?

Yes, the key to that is just having you data in a multi-dimensional array, and using this->EE->TMPL->parse_variables() (see docs).

Is it possible to create some sort of addon whose data is stored on a different database?

Sure, I'm pretty sure this should work (based on the CodeIgniter docs):

$config = array(
    'hostname' => "localhost",
    'username' => "myusername",
    'password' => "mypassword",
    'database' => "mydatabase",
    'dbdriver' => "mysql",
    'char_set' => "utf8",
    'dbcollat' => "utf8_general_ci"
);    
$this->EE->custom_db = $this->EE->db->load->database($config);   
// Now use $this->EE->custom_db->query(), etc

Since this won't be using Channels, how would I make my back end interfaces appear in the Control Panel?

You'd have to build the interfaces yourself, using "view" files inside your add-on, which can then use EE's helper classes to build forms, tables, etc for display. (See the module tutorial for some guidance.)

Will I be able to loop through the entries like I do with Channel entries (using tag pairs)?

Yes, the key to that is just having your data in a multi-dimensional array, and using this->EE->TMPL->parse_variables() (see docs).