If you have a large number of references to this structure, it may be worth the trouble to build an index (%referer) to it.

use strict;
use warnings;
use Data::Dumper;

my @lecshun = (
    ['namea', {
        package => 'gema',
        index   => 'dexia',
    }],
    ['nameb', {
        package => 'gemb',
        index   => 'dexib',
    }],
);

my %referer = (
    namea => $lecshun[0][1],
    nameb => $lecshun[1][1],
);

print Dumper \@lecshun;
$referer{namea}{new_key} = 'new_value';
print Dumper \@lecshun;
[download]