Edit conflicts and 409 vs. 412 responses

We have a REST API which is used to work with the application backend. We need to implement a conflict prevention function, which would on edit request (POST/PUT) would check if the record was not modified between the client's last read of it and now, and if it were, would tell the client there's a conflict.

The question is how to send the conflict check tag (which most probably would be a timestamp, but we don't want to mandate that) and how to return the error.

We would like to use standard REST patterns as much as possible, so here the solutions we considered:

Using If-Modified-Since. The problem here is that it mandates using a timestamp and also the spec says you MUST return 412. We'd like to return more specific 409 code, to indicate it is an edit conflict, as described in the spec, instead of much more generic 412 which can be caused by other reasons. This would also make it much easier for the client to have special handling for edit conflicts, because they would have dedicated error code.
Using If-Match. Better since we can use any data attached to it, but again the spec mandates using 412 even though 409 fits our case better. Also, the spec suggests If-Match is linked to Etags, and we don't use Etags for our data because it's not feasible to calculate proper Etag for every record. We have the tag that we would be using for checks as part of the record data, but it is not sent as ETag and existing clients do not process ETags, so we wouldn't want to impose this new requirement on the clients if possible.
Using custom X-Header. This would work just fine and would be pretty easy for the clients to add but we'd prefer using standard REST means if possible.

So, what is the recommended way in this case? Is there a way to use standard REST means, respond with 409 and have it all nice and clean?

Basically, if you have If-* preconditions in the header, you must return 412. Even if you use custom X-Header, it only means that header has no definition where it says it must return 412. If the custom header is used as a precondition, you should return 412 according to its definition:

This response code allows the client to place preconditions on the current resource metainformation (header field data) ...

E-Tag is usually only sent in requests as part of If-* preconditions, so if you want 409 then you won't use E-Tag.

If you want to use 409, just put the preconditions or postconditions in the request body, not a header. WebDav returns 403 or 409 when a condition fails. 409 when the client might be able to fix the request. See RFC 3259.

So, to conclude: Use 412 if your preconditions are in a header, otherwise use 409.