They suggested writing an address book and accessing it, and I realized that this could be a great way to learn about hashes.

You could do this with hashes, Data::Dumper, and do, or you could do it with DBI. If you want to learn to do database stuff, DBI is good way to go.

Actually it sounds like a reasonably good excuse for learning Class::DBI. For the backend, yeah, MySQL (with DBD::mysql) is fine for your requirements or you could even use DBD::SQLite. I assume you know how to install modules from the CPAN?