When I have done this in the past, I experemented with CPAN and creating a localy built debian package that contained everything before deciding on local::lib and checking the local lib into source control.

The developers on the project would run CPAN against the local lib whenever they needed to add new libaries, or update existing ones. Deployment on the servers was a simple svn checkout of the relevant tag.

In the main it worked well, but there where occasions where perl packages that compiled binary XS code would break things quite comprehensively for other platforms, while appearing to work fine for the platform it was compiled an tested on. If you have more than one OS or processor archetecture on your servers then take a look at node 942112 where I have described the problem in more detail.