п.1 обходом слева направо и сверху вниз найти свободную область размером 1х1
п.2 обходом слева направо и сверху вниз найти свободную область размером 2х2

select x-2+1 startX, y-2+1 startY, x endX, y endY
  from (
     select @num:=if(y=@y+1 and @x=x,@num+1,1) nY, @y:=y y, @x:=x x, nX
       from (
          select @num:=if(x=@x+1 and y=@y,@num+1,1) nX,@x:=x x, @y:=y y
            from table1 T, (select @x:=0, @num:=0, @y:=-1) A
           where status=0 and id<=100
           order by y, x
       ) B
  where nX>=2
  order by x, y
 ) C
 where nY>=2
 order by y, x
 limit 1

update table1 T
  join (наш запрос) N
    on T.x between N.startX and N.endX
   and T.y between N.startY and N.endY
   set status=1