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 <some_table>
WHERE row1 IS NULL AND row2 > <some value> 
ORDER BY row2 LIMIT 100;
UPDATE <some_table> SET row1=<some value> 
WHERE row1 IS NULL AND row2 > <some value> 
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 <some_table>
WHERE row1 IS NULL AND row2 > <some value> 
ORDER BY row2 LIMIT 0,100;
UPDATE <some_table> SET row1=<some value> 
WHERE row1 IS NULL AND row2 > <some value> 
ORDER BY row2 LIMIT 0,100;  

On WebServer2 run

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

On WebServer3 run

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

All the way to WebServer9, run

SELECT * FROM <some_table>
WHERE row1 IS NULL AND row2 > <some value> 
ORDER BY row2 LIMIT 800,100;
UPDATE <some_table> SET row1=<some value> 
WHERE row1 IS NULL AND row2 > <some value> 
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.

Use SQL Profiler to trace your deadlocks and find a few example queries that are the root cause.

Then copy that SQL to SSMS and view the execution plan for it.

Look to see what kind of locks are being held when the query runs.

It's almost certain that you are experiencing table locks - actually, as you state, someone removed row-level locks and page-level locks.

You have options:

1. Modify your SELECT statement to use READ UNCOMMITTED or (nolock). This means this query can read dirty data. Only you will know whether this will be acceptable with your data set - very often, it is fine to have dirty reads and doesn't impact the functionality of the system.

2. Use row-level locks. You can force these using a query hint.

3. Use row-versioning - this option means the updates operate on a different version of the rows to the ones that the SELECT statement is reading from avoiding deadlocks altogether.

You can find out more details about row versioning and other deadlock reducing techniques here.