|Do you know where your variables are?|
I believe CPAN should be introduced much sooner. You don't have to know how to write classes yourself in Perl to use object oriented modules, and various modules employ object orientation to varying degrees. You can start with simpler interfaces and gradually work your way to more completely object oriented modules.
At this point, they can already work with highly improved efficiency.
Then, you can introduce the features that make these work, one by one; starting with package to write simple libraries, and gradually adding nooks until you naturally reach bless. Because they've already seen how each of these crannies looks from the module user perspective, your pupils are likely to grok their purpose easier.
Of course, the premise to all this is that they need to understand references. So that would be the first thing on your list; and logically, too, if you ask me, since any non-trivial datastructure - and therefor any well written code for a non-trivial task - requires them. Remember the foremost principle to good software design is good data structure design: the necessary code will nearly naturally follow from a well designed data structure. Arrays of arrays or hashes are much better than working with parallel arrays, an awfully ugly workaround for not having references. It is incredibly important to build this skill.
So you have the following order:
To me that looks like a natural way of going about it, and I believe it also offers the most practical value at any point in time. Everything your pupils learn will be immediately useful to them. Which means that they won't get bored with theorizing, so that it'll be easier to maintain concentration and build understanding. The bottom line is greater rewards for the pupils and, let's not forget, easier lessons for you and them.
That's my thoughts after 15 minutes of thinking about it. :-)
Makeshifts last the longest.