Checking for 'Foo's existance is not cumbersome in the "amount of work being done" sense, but grepping is somewhat.

Hash lookups occur in O(1) time, so checking the existance is not time consuming. However, keys in list context takes O(n) time (essentially the time it takes to generate the list), and grep also takes O(n) time (the time it takes to thumb through the entire list). So you're looking at O( n + n ) time, or O(2n), which isn't the end of the world; it's not as bad as O( n log n ), or O( n**2 ), or worse. But just keep in mind that you're generating the list, and paging through it, in two separate steps.

There's not much you can do about that. You can't ask for all the keys except 'foo' in a single operation. One solution, however, may be to simply keep track of the keys in the first place. Of course this means there's additional overhead of creating and maintaining an array of keys. So the benefit (if any) depends on how often you create and modify the list of keys, versus how many times you use it. If you create and/or modify infrequently, and use frequently, maintaining a separate list of keys makes sense. If you create and modify frequently, and use seldom, the separate list is probably not going to be much benefit.

By the way, my initial reaction was to come up with something like this, using a slice:

my @values = 
        @hash{
            exists( $hash{mystest} ) ? 'mytest' : (),
            grep{ $_ ne 'mytest' } keys %hash
        };
[download]

As you can see, it's pretty much the same as one of your solutions, except that it simply returns a list of the values.

Another solution could be to use splice, and unshift to reorganize an array of keys. Again, this is mostly useful if you use the list of keys a lot, but modify it infrequently.

Update:
You know, as I thought about this another moment or two, it occurred to me that maybe there would be some benefit to scrapping the whole hash solution, and going with a heap. Heaps excel at keeping one item sorted at the top, and the rest 'just there', in a semi-sorted order waiting for their turn at the top. There are several good heap implementations on CPAN. Maybe a heap is too much fiddling though, it all really depends on how critical it is to optimize this one particular exercise. If this piece of code is really time critical, and if your particular set of criteria would benefit from a heap, then maybe that's the right choice.

Oh, and forget about any notion of hash ordering. Hashes aren't ordered, and you cannot depend on order being preserved. They don't have order. Assume that with the above piece of code, you're guaranteeing the order of one element, and not caring at all about the order of the rest.