Do I violate RESTfulness when using POST as UPDATE OR CREATE
Given the requirement other departments have for our REST API they would like to use POST not just for CREATE but for UPDATE OR CREATE. I know in a RESTful API PUT could or should be used for that, but because clients have to update information that is used to build the URI, we cannot use that. It would change the URI and make PUT not idempotent anymore... (the old URI would not exist after the first PUT).
tl;dr we cannot use PUT
In the HTTP/1.1 specs POST is defined as
The POST method is used to request that the origin server accept the entity enclosed in the request as a new subordinate of the resource identified by the Request-URI
but also
The action performed by the POST method might not result in a resource that can be identified by a URI.
To stay RESTful I would explain the update functionality as an Deletion of the old element and then a Creation of the new one, which would be an acceptable functionality for POST I would say.
We would return a #201 when creation was successful and a #200 when it was just an update.
In our API it is "possible" to address the right element without the URI (e.g. for updating it with POST), because all the URI building primary key parts are in the resource body, so the API knows which element the client wants to access.
Example
(This is just an example of the behavior for POST. Not for the data structure of the resource. Of course using PUT would be completely right for /cars/)
POST /cars/ HTTP/1.1
<car>
<id>7</id>
<status>broken</status>
</car>
response: #201
and then
POST /cars/ HTTP/1.1
<car>
<id>7</id>
<status>fine</status>
</car>
response: #200
now a GET on /cars/7 would return the following:
<car>
<id>7</id>
<status>fine</status>
</car>
Answer
"Violating RESTfulness" is not strictly defined.
A good reference to degrees of REST-like behaviour in an interface is the Richardson Maturity Model which splits degrees of support for REST ideals into 4 tiers (with 0 being "not REST at all" and 3 being "completely REST, but hardly anyone does this yet")
Your choice breaks only slightly with RESTful HTTP-based design at level 2 within this model. However, it is the kind of compromise that many real-world projects have to contend with.
POST is open-ended enough that it can be idempotent if you wish, but HTTP does not require it to be. So you have not broken with HTTP, just missed the opportunity to use the more germane PUT method. The reverse situation, using PUT for a non-idempotent part of the API, would be more problematic.
As a personal opinion, I think that if you remain self-consistent when handling the different HTTP methods and routes, and document this change to expectations clearly, then you can reasonably call your API "RESTful". I think the response code split 200/201 is enough that a self-consistent client could be written. Although I would prefer to see both create and update as PUT here, it's not something that would cause me more than a moment's pause.
You might consider supporting update or create on the collection route (POST /cars in your example) as suggested, plus update on the item route (POST /cars/7). The concept of "update or create" is common enough in database and ORM frameworks, that it would be easily understood. A client could also use the latter update-only route in confidence that it would not accidentally auto-create a new record.