Can this algorithm on removing $1$'s from a $(0,1)$-matrix fail?
I'm not sure about whether this works, but I'd be doubtful.
Another way to express this problem is finding maximum partial matchings in a bipartite graph. (Just interpret the matrix an adjacency matrix for the graph). By a maximum partial matching I mean a maximal-sized set of edges no two having a vertex in common.
The reason for my scepticism is that if your algorithm worked, then it would give an algorithm for finding the solution in the situation of Hall's marriage theorem. Your algorithm is "monotone" in the sense that it adds edges but never removes them, but all the algorithms I have seen for Hall's theorem, one needs to remove edges in certain circumstances in the process.
For the problem is hand, an algorithm comes from any that solves the maximum flow problem in a network. Attach a source to each vertex on one side of the bipartition and a sink to each vertex on the other side. Give all edges unit capacity and find a maximum flow.
Yes. Consider a large square matrix with two large square blocks filled with ones and one empty row and one empty column. Delete one one from each of the blocks off the diagonal, and place a corresponding one in the empty row and column. You now have one row with two elements, the rest having many elements, and one column having only two elements, the rest having many. Your procedure will deal with the sparesely populated row and column first. Permute the rows and columns so that you procedure links the two choices with different blocks. Now the remainder of each block has one more row than it has columns or vice versa, as a perfect matching cannot exist. It is easy to see however that a perfect matching existed before your algorithm matched the sparse row and column.
Diagram to give an example for deinst's answer. I tried putting this in a comment, but it stuffed up the formatting. The Xs marks ones that give a complete match
X01100001
1X1100000
11X100000
111X00000
00001011X
0000X1110
000011X10
0000111X0
01000X000
Now, suppose we take the two squares marked by Y's
*0**0000Y
111100000
111100000
111100000
00001011*
00001*110
00001*110
00001*110
0*000Y000
We have two 3 by 4 squares left, so we can take 6 more items. This give a total of 8 instead of 9. We can enforce those two blocks to be taken by using a permutation.