my @order;
for my $key (keys %HoA) {
  if ($key eq 'Foo') {
    unshift @order, $key;
  } else {
    push @order, $key;
  }
}
for my $key (@order) { ... }