Here is what I ultimately had to do to figure out what "other query" caused the lock timeout problem. In the application code, we track all pending database calls on a separate thread dedicated to this task. If any DB call takes longer than N-seconds (for us it's 30 seconds) we log:
-- Pending InnoDB transactions
SELECT * FROM information_schema.innodb_trx ORDER BY trx_started;
-- Optionally, log what transaction holds what locks
SELECT * FROM information_schema.innodb_locks;
With above, we were able to pinpoint concurrent queries that locked the rows causing the deadlock. In my case, they were statements like INSERT ... SELECT
which unlike plain SELECTs lock the underlying rows. You can then reorganize the code or use a different transaction isolation like read uncommitted.
Good luck!