MySQL InnoDB locking on combined UPDATE-JOIN statements on querying statements which contain an UPDATE combined with JOIN, we are getting the following errors:

Statements writing to a table with an auto-increment column after selecting
from another table are unsafe because the order in which rows are
retrieved determines what (if any) rows will be written.
This order cannot be predicted and may differ on master and the slave.


These statements finally turn into deadlocks and kill other statements trying to access the same table (update: it doesnt even seem the queries care about the timeout, because some deadlocks occure after 5-20 seconds).

innodb lock wait timeout = 150
binlog_format = STATEMENT


I can't believe that MySQL offers the possibility to UPDATE a table depending on another table (UPDATE x JOIN y.. SET x.val = 1 WHERE y.val = 1), but can't handle it on InnoDB-Cluster.

Any Ideas?
Without seeing your specific query and table structures, it's not possible to give a really precise explanation or to know whether MySQL is being unnecessarily cautious; however, the message you are seeing appears to be a consequence of using binlog_mode = STATEMENT which you should be able to safely change to binlog_mode = MIXED. 

The problem is, if your update query isn't deterministic, and is replicated by executing the same query on the replica -- as opposed to simply sending rows changed by the query to the replica, as would likely be done in MIXED binlog format (and certainly in ROW format) -- then the execution on the replica might be optimized differently and result in your tables being different.

If that is the case -- or if MySQL thinks that is the case -- then it is correctly preventing you from running a query that might not replicate properly because of your chosen binlog_mode.

The innodb_lock_wait_timeout value is not related to deadlocks.  It is a timer for queries that block waiting for row locks, but which could eventually succeed because the lock requests aren't incompatible with any other locks.  This timer affects queries which fail this:

ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction 


A deadlock, on the other hand, is a completely different thing.

Deadlocks have no timer, because by definition, a deadlock will hang infinitely.  So, as soon as they are detected, MySQL will kill as many queries as necessary to resolve the deadlock, typically killing the one(s) that did the least amount of work so far.

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction


Deadlocks occur when two (or more) threads try to do mutually-incompatible things that cannot ever possibly complete, because each of them has to wait for the other one to finish before it can proceed.

http://dev.mysql.com/doc/refman/5.5/en/innodb-lock-modes.html