Well, your code is probably organized into subroutines with some defined set of inputs and outputs, right? So, test those subroutines! Create a set of sample inputs and expected outputs. (This is a good way to help decouple your subroutines, too.)

Remember - testing an object still involves testing a bunch of subroutines. Yeah, there's some state and it can be easier to envision it, but it's still just a bunch of subroutines.

If you're dealing with testing scripts and the like, I'd point you to Test::Cmd and Test::Cmd::Common.