|Welcome to the Monastery|
Personally I think that if you gave them the task of creating a "standard" module for a relatively simple tied object, buildable with tests, implemented using a simple algorithm like a binary tree (or better a right threaded binary tree) then you would kill a whole lot of your birds with one stone.
A tie is of course object oriented by definition, but with a very clearly defined interface with the added possibility of being able to use the item in a non tied pure OO fashion, or of adding supplemental utility methods.
A self referential object like a threaded binary tree (and im thinking of a threaded tree, mostly because it makes FIRSTKEY, NEXTKEY (iterators) much simpler to implement without being too complex in terms of data structure, requiring only the addition of flag field to a node ) is obviously heavily referential (and you could make things interesting by getting half of them to use array based structures, and half to use hash based structures) and as it involves back references it exposes the idea of object destruction and scope effects.
By building a module such as the above starting from h2xs, as specified in an easily accessable and readable module like Tie::Hash, having them write tests with Test::More and the h2xs/MakeMaker system they would learn the process that CPAN automates, learn how to build tests and installable modules, write pod, and generally improve the world. ;-)
I guess if heavily referential structures werent to your taste, a reimplemented (hmm, i cant find it on CPAN) character array tie might do nicely (you know treat a scalar as an array of chars (but with more interesting semantics))
updated: Couple of spelling and gramatical errors. It was late... :-)