One cheesy idea I've exploited: keep your methods as subrefs in a lexical hash in the module's file. Have AUTOLOAD take care of actually dispatching to the methods when they're called. The subs are unreachable outside of the module unless you pass a reference outside somehow.

It can make your code hard to read (and subclass, and...), but if all you want is privacy...