I like the closure approach suggested by
stvn. It comes with a small performance penalty because of all the function calls (7-20% depending on the dataset and spread), but it makes the code much easier to read/maintain.
On a related note - it would be good to add some documentation that describes your strategy. It isn't immediately apparent, and I had to re-read the code a few times before it was clear.
Found one problem: the following line should test whether $last_key is defined, to avoid problems when your data contains an empty string or '0'.
if ( $last_key and ( $last_key ne $_->{ $key_name } ) ) {