Assuming each UPDATE statement hits only one table... (It gets more complicated if you are doing a multi-table update.)...
Do the update in chunks:
Plan A: (assumes auto increment with no gaps)
$a = 1
Loop:
UPDATE tbl SET ... WHERE id BETWEEN $a and $a+999
$a += 1000
exit when rows affected is 0 -- a gap of >1000 would mess up this test
Plan B (assuming char string id):
$a = SELECT MIN(id) FROM tbl;
Loop:
$z = SELECT id FROM tbl WHERE id > $a ORDER BY id LIMIT 1000,1
exit loop if no $z
UPDATE tbl SET ... WHERE id >= $a and $id < $z
$a = $z
endloop
UPDATE tbl SET ... WHERE id >= $a -- last bunch
Tune the 1000 (and 999) to make the lock time tolerable.
Caveat: During the UPDATE process, SELECTs will be seeing some updated rows, some non-updated rows. This could be a problem.
BTW, similar tricks work well for DELETEs (MyISAM or InnoDB).