This is interesting. It reminds me of Test::MockObject and the more recently uploaded Test::MockModule in functionality, but for more general purpose use. I do have a few comments though.

To start with the name is horrible. "Stubber" is just a weird word and you are probably better off just using Module::Stub which is not yet taken.

Second, since use statements run at compile time, I would suggest offering an alternate interface for compile time stub-ing. Something like this.

 use Module::Stubber (
          'Foo::Bar' => {
              new => sub { bless {}, $_[0]; },
              stringify => sub { "$_[0]"; }
          });
[download]

The code to do so would be simple enough.

Also I would be sure the stub module is properly added to the %INC hash, otherwise require and use will try to load the real module. (you may have already done this, but you didn't post code, so I don't know).

Your description describes a number wonderous possibilites which your module opens up to it's user (hooking into CPAN, alternate @LIB directories, etc). I would create some of those possibilities, either as subclasses of your module or as plug-ins of some kind. Otherwise they are just empty promises. Doing so will also serve to illustrate the use of your module far better than any textual description can. It will also increase the usefulness of your module to a larger audience for whom writing such code is out of their range of skills.