I think Test::Class is the way to go, if you expect people to use your code as the base for their code. If you do this, consider distributing your test modules along with the other modules.

The only other thing I can recommend, without seeing code or design questions, is to consider not hard-coding the names of classes used by other classes. That is, for the purposes of testing, it should be really easy for me to use Test::MockObject::Extends to wrap one of your classes to override the one or two methods that use the database or access the network, or do something else beyond what I want to test.