Weak references are still what I would recommend.

You want a double data structure. One cache with weak references which you use when accessing possibly cached objects. And one data structure to keep references to objects that you want to keep from expiring. Flush the second one as appropriate, access through the first. Perl's GC does everything else for you.