Personally I would be inclined to introduce things in this order.

Basic introduction, how to write a program, how to run it. Hello World level.

Scalars.

Arrays.

Functions.

Strict and my.

Taking user input.

Scalar vs list context. (Arises very naturally while trying to read STDIN into various things.)

Hashes.

etc.

The route is very direct. Straight to the simplest construct in which you can see why my is useful, then straight to how to protect yourself. The detailed scoping rules, loops, blocks, and context can all come after I hit the basic habit I want people to have. How that habit intertwines with each additional concept can be covered when I hit the concept in question...