A quick and dirty fix is to just strip off any leading "::" before printing:

sub parsetree {
    my $ref = shift;
    my $txt = shift;
    foreach my $key ( keys %{$ref} ) {
    if( ref( $$ref{$key} ) =~ /HASH/ ) {
        parsetree( $$ref{$key}, $txt."::".$key );
    } else {
      my $out = $txt . '::' . $key . '::' . $$ref{$key} . "\n";
      $out =~ s/^:://;
        print $out;
    }
    }
}
[download]

This will produce (Update: closer to) the requested output, so long as "order" doesn't matter.