Key generation that is random, unique DB-wide and bounded

I have three main constraints for int8 key generation:

• Keys need be unpredictably random
  • Number of rows created should not be calculable
  • Order of row creation should not be calculable
• Keys need to be unique across the entire db
  • Future table merges should not require changing keys
  • Future Table-Per-Class superclass additions should not require changing keys
• Keys need to be bounded
  • These keys will be base58 encoded in various places such as URLs
  • Range will be narrower at first but should be adjustable in future to meet demand

I have heard of a few approaches to tackling at least some of these constraints:

DB-wide serial8

Does not meet the first constraint, but meets the second and third constraints.

DB-wide serial8 combined with a cipher

If the cipher key is leaked or discovered at any point then this becomes just DB-wide serial8, since the cipher key can't be changed without changing all the existing keys.

UUIDs

Does not meet the last constraint due to their 128-bit nature, but meets the first and second constraints.

Set default to floor(random() * n)

Does not meet the second constraint due to collision risk, but meets the first and last constraints.

Using random combined with a keys base table to keep track of all the keys

This does sort of meet all the constraints. However if a duplicate key is generated the insertion will fail. I am also concerned about any performance / locking issues.

If there is a nice way to make this re-roll until a non-colliding key is found, with good performance, then this would be an acceptable solution.

---

What is the best way to generate keys in PostgreSQL that meets the three criteria I listed?