The solution of fencing tokens on the storage layer that's proposed there, just pushes the problem one layer down - you'll still need the storage layer to be consistent for this to work. Also it means it should be aware of those semantics, which complicates thigns. Redlock has non incremental tokens, so I guess it can be used as well. Read @antirez's reply above.
Interestingly, even though HBase uses Zookeeper for coordination, it does not use it for fencing. Instead, fencing is handled by atomic "log-rolling" operations on the HDFS namenode, which can be configured to use its own quorum-based journal. (The equivalent of a "token" is the monotonically-increasing namenode operation sequence number.) So the principle is the same: the system responsible for doing mutual exclusion, and the system that actually stores the data, must be coupled.