HBase: atomic 'check row does not exist and cr

I suggest this should be one of common cases but probably I use wrong keywords when googling around.

I just need to create new table record with completely random key. Assume I obtained key with good randomness (almost random). However I can't be 100% sure no row yet exists. So what I need to do atomically:

Having row key check no row exists yet.
Reject operation if row exists.
Create row if it does not exit.

Most useful piece of information I found on this topic is article about HBase row locks. I see HBase row locks as suitable solution but I'd like to do it better way without explicit row locking.

ICV looks not suitable because I really do want key to be random.
CAS would be great if they could work on 'row does not exists' condition but it looks they can't.
Explicit row locks have disadvantages like issues on region split.

Could somebody please add useful advice? Preferable API is Java based but actually it is more about concept rather than implementation.

'Good enough' solution for this case happened to be based on checkAndPut() method. What I intended to do is new row insertion with key duplication check and for individual inserts solution is perfect:

HTable checkAndPut() method can check certain column is not set (check it for null value).
As rows anyway contain some 'ID' field which is mandatory for all objects (you can use any other field that you always set for your object) it is possible to check if row exists.
Put object passed to checkAndPut() is to contain initial object state with mandatory field set.

Well, for bulk insertion (what I really needed) it happened to be too slow so I moved to UUID used as row keys without any checks on new row insertion. For me it is much better. The only consideration in this case is really good random generator. Standard Java java.util.UUID class contains everything I need including it is based on somewhat slow but pretty strong java.security.SecureRandom generator.

Just note: it looks like HBase user row locking feature is going to be dropped due to security / other risks related to its usage.