The line-covering step in the Hungarian algorithm
OK, after reading this much more complicated explanation of the same algorithm, using bipartite graphs instead of matrices, I realized how to find the smallest number of rows/cols. 

Given the matrix, create the "graph of zeros" - a bipartite graph where the rows are on one side and the cols are on the other side, and there is an edge between row and column iff there is a zero in their intersection. Then, our problem becomes finding a smallest vertex covering of this graph. 

Based on Koenig's theorem, a smallest vertex covering in a bipartite graph can be found using any algorithm for finding a largest matching in the graph, in polynomial time.