MySQL InnoDB locking on combined UPDATE-JOIN statements
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