Good point to note that you can also use non-member variables within a with. But in the way I envision it working, Perl would do The Right Thing. If only it would work. Here's a quick description:
with takes a hashref and a coderef. It goes through the hashref and creates package variables in the "With::" namespace that point to the hash elements. Then it executes the coderef in the With package space.

Sadly, I don't think it can be done. Even in a coderef executed within a package, Perl considers the unqualified variable names to be in main (or wherever the coderef was created). And while my glob-fu is shaky, I don't think it's possible to make a symbol table refer to another hash, so that changes to package variables actually affect members of the hash.

Here's an eval solution that turns the members into references with the same names, so the user accesses them as, e.g., $$a:

use strict; 

my %hash = ( a => 1, b => 2, c => 3 );

sub with(\%&) {
  my ($href, $cref) = @_;
  my $cmd = join "\n",
    map sprintf('local $::%s = \\$href->{%s};', $_, $_),
    keys %$href;
  eval $cmd . '$cref->()';
  warn "$@: $cmd\n" if $@;
}

with %hash,
  sub {
    $$a = 'changed';
    print "B=$$b\n";
  }
;

use Data::Dumper;
print Dumper(\%hash);
[download]

I always feel dirty after using a string eval, though.