BEGIN blocks fire at compile time, just like use statements. (Camel 3 points out that "use" is just a fancy BEGIN block. See page 465.) They also go in order, top to bottom.

The point of changing @INC at compile time is to make sure that the new paths are there when modules are loaded. If you don't do that at compile time (with either BEGIN or use lib), it won't affect any of your modules.

Can I say "compile time" enough?

Update: There's no effective difference between use lib and the BEGIN block (with unshift), except that lib adds some architecture-dependent directories, if they exist. I was only addressing the "@INC is global" question. (Short answer: it is, but the important thing is *when* it is changed.)