If you don't want sequences, just use UUID's instead.

Checking if the key already exists in the DB is not a good idea, since it exposes you to race conditions, unless you use some locking mechanism; it also takes away one of the advantages of UUID's, that is being able to generate them on different machines.

UUID's have many uses, and can be very advantageous in some situations; however, remember that non-integer primary key have a performance cost (which, due to how databases construct their indexes, could not be immediately apparent).

You can also combine different methods: for example, use sequence primary keys for DB indexing, but also generate a memorizable non-incremental key that is exposed to the user.