A pure functional recursive approach:

sub flatten
{
    map
    {
        my $k = $_[0][$_*2];
        my $v = $_[0][$_*2+1];
        !defined $v ? [$k] :       # one scalar leaf
        !ref $v ? ([$k],[$v]) :    # two scalar leafs
        map [$k,@$_], flatten($v); # scalar key and arrayref val
    }
    (0..$#{$_[0]}/2) # iterate over input list pairwise
}

my @a = flatten( $data_struct );
print "@$_\n" for @a;
[download]