Use a lithium ion battery from a laptop, for a small project?
The problem, as you say, is complete depletion.

It doesn't just ruin the life of the battery.  It ruins the battery.

If a Li-ion or Li-poly battery gets completely depleted it is dead.  Full stop.  Replace it.

If you were to use Li-ion or Li-poly batteries then you will require some kind of battery management system to shut off the power before the battery gets completely depleted.

There are dedicated ICs around to do this exact job.  For example - take a look at Texas Instruments' range of Battery Monitor chips