Minimize locking on UPDATE with multiple WHERE columns
You will need to lock all the rows yourself before each UPDATE.

See the MySQL Documentation on SELECT ... LOCK FOR UPDATE. This performs an exclusive lock on all the rows you pass through. Then, you can follow up with the needed UPDATE against the table.

In your particular case, you would do this:

SELECT * FROM &lt;some_table&gt;
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 100;
UPDATE &lt;some_table&gt; SET row1=&lt;some value&gt; 
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 100    


INDEXING


You should index the table fully to support all possible ways you will be querying the data. Notwithstanding, you must alternate between SELECT ... FOR UPDATE and UPDATE.
Since you have both row1 and row2 in the WHERE clause, you should have an index with both columns in it.
There is one warning: If these columns are indexed, expect some slowness because the column is being updated and the BTREE index pages are being updated per row. You should also expect rapid growth of the insert buffer section of ibdata1 (See InnoDB Map)


I have many posts on the subject of SELECT ... FOR UPDATE and SELECT ... LOCK IN SHARED MODE.


Case Study I went through with @RedBlueThing


Reasons for occasionally slow queries?
Trouble deciphering a deadlock in an innodb status log
Will these two queries result in a deadlock if executed in sequence?

Aug 08, 2011 : Are InnoDB Deadlocks exclusive to INSERT/UPDATE/DELETE?
Oct 18, 2011 : Preventing mysql deadlocks in your php application that uses SELECT… LOCK IN SHARE MODE
Jan 02, 2012 : LOCK IN SHARE MODE
Nov 19, 2012 : How long can Deadlock info hold in innodb status page?
Dec 13, 2012 : MySQL InnoDB locks primary key on delete even in READ COMMITTED
Feb 03, 2013 : MySQL InnoDB locking on combined UPDATE-JOIN statements
Mar 12, 2013 : How I prevent deadlock occurrence in my application?


UPDATE 2013-03-17 19:21 EDT

Since you have 9 WebServers hitting the DB Server, try this

On WebServer1 run

SELECT * FROM &lt;some_table&gt;
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 0,100;
UPDATE &lt;some_table&gt; SET row1=&lt;some value&gt; 
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 0,100;  


On WebServer2 run

SELECT * FROM &lt;some_table&gt;
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 100,100;
UPDATE &lt;some_table&gt; SET row1=&lt;some value&gt; 
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 100,100;  


On WebServer3 run

SELECT * FROM &lt;some_table&gt;
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 200,100;
UPDATE &lt;some_table&gt; SET row1=&lt;some value&gt; 
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 200,100;  


All the way to WebServer9, run

SELECT * FROM &lt;some_table&gt;
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 800,100;
UPDATE &lt;some_table&gt; SET row1=&lt;some value&gt; 
WHERE row1 IS NULL AND row2 &gt; &lt;some value&gt; 
ORDER BY row2 LIMIT 800,100;  


You will have to place some PHP header file that unique identifies which machine runs which version of the query.