If you are dead-set against Tie::IxHash, then you can always try this bit:

use strict;
use warnings;
use Want;
sub create_ordered() {
    my (@keys,@values,%order);
    my $x=0;
    return sub : lvalue {
        if (want('LVALUE')) {
            if (!exists $order{$_[0]}) {
                $order{$_[0]} = $x++;
                push @keys, $_[0];
            }
            $values[$order{$_[0]}] = want('ASSIGN');
            lnoreturn;
        }
        elsif (want('RVALUE')) {
            rreturn @keys if wantarray;
            rreturn $values[$order{$_[0]}];
        }
        return;
    }
}


# sample use:
my $hash = create_ordered;
$hash->("first") = "one";
$hash->("second") = "two";
$hash->("third") = "three";
$hash->("fourth") = "four";
$hash->("second") = "tutu";
my @keys = $hash->();
foreach (@keys) {
    my $x = $hash->($_);
    print "$x\n";
}
[download]

However, this is *very* cumbersome to use. For instance, you can't delete keys and you can't hash-splice. You also need to be very careful about context. Is there any reason you can't bundle Tie::IxHash with your application? Or at least copy the source code, put it at the top of your script with an author credit?