UPDATE/WARNING: I was curious how difficult an eval solution might be, but as merlyn points out, this code is dangerous and slower then other safer solutions. Despite merlyn's staunch reply about not using it, it is still a soltuion and we all know TIMTOWTDI. The original poster made it clear that he understood eval was a bad idea. I learned my lesson, I will not post code just to post code, bad trs80, bad.

I know you requested a non eval solution, but I couldn't restrain myself.

use strict;
use warnings;

my $structure = {
    stuff => { 


        hierarchy => { 
            album => { 
                bar => 'the right one',
               },
        },  
    },
};

my $path = [ 'stuff', 'hierarchy', 'album' , 'bar' ];

print get_structure_value($structure,$path) , "\n";
$structure = return_new_structure($structure,$path,'new value');
print get_structure_value($structure,$path) , "\n";

sub make_eval {
    my ($path) = shift;
    my $string = "\$hashref->";
    $string .= "{$_}" for @$path;
    return $string;
}

sub get_structure_value {
    my ($hashref,$path) = @_;
    my $string = &make_eval($path);
    return eval($string);
}

sub return_new_structure {
    my ($hashref,$path,$set) = @_;
    my $string = &make_eval($path); 
    eval("$string = '$set'");
    return $hashref;
}
[download]

Excuse the verbose sub names, I wanted it to be clear what each did, I created a sigle sub to being with but I didn't like the interface, I think this makes it clear what you are getting back.