Unless keys() can be switched to a test mode to produce predictable results (doesn't need to be sorted, just give me something predictable, like before perl 5.17), what are the options?

To test hash_serialize():

I would deserialize it to memory, and compare with original hash (with something based on "sort keys" or with cmp_deeply).

However this violates some ideas of unit testing (while it's ok for integration testing).
If it's worrying you - test it for 1-element hash and 2-elements hash (yes, all 2 permutations), and stop. Do other testing with deserialization.

To test other code, which uses hash_serialize():

mock (fake) hash_serialize().