How to UPDATE data without locking every record the search encounters?
UPDATE a SET col4 = 3 WHERE col1 = 1 AND col2 = 2 AND col3  = 3;

Needs this composite index:
INDEX(col1, col2, col3)  -- in any order

So, if you start it with col1, col2 (in either order), that index will also work nicely for
UPDATE a SET col4 = 2 WHERE col1 = 1 AND col2 = 9999;

If, by &quot;We have indexes on all the columns&quot; you mean single-column indexes, then those are wasted and in the way.  MySQL will use only one index.  It will pick among (col1), (col2), (col3) looking for the most selective.  Then it will scan all the rows with, say col1 = 1.  This is likely to be a lot more rows than you need to UPDATE.
With the composite index I recommend, it will go straight to the row(s) that match all of the WHERE clause.  This will be many fewer rows, thereby decreasing the likelihood of a deadlock.  Also, it will be much faster, which also decreases the chance of a deadlock.
Regardless, your could should check for errors and re-run any transaction that hits a deadlock.