Pick the longest stick

Ruby, 83 75 68 66 63 bytes

f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

Defines a function f which takes the 2D array form as input.

I'm starting at the bottom left, keeping track of maximum stick length (actually, minus that) and the corresponding column. In each column, if there are still 1s above the previous maximum stick length, I walk up the stick to the end and remember the new maximum length and column. That means that I'm iterating once along the columns and at most once along the rows (specifically I'm iterating as far as the maximum stick length), which is precisely O(m+n).

Python 2 - 71, 69, 73, 75 81

j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J

GolfScript, 45 chars

:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

Takes input as an array of strings, returns (0-based) index of tallest column. It runs in O(rows + columns) iterations, and each iteration should take essentially constant time (at least assuming constant-time arithmetic). The only array/string operations done within the loop are element lookups (=) and taking the length of a string (,), both of which take constant time in GolfScript.

Try it online.

Explanation:

Like most of the solutions here, this code works by starting at the lower left corner of the matrix, walking up or right depending on whether the current element of the matrix is 1 or 0, and keeping track of the column where it last moved up.

At the beginning of the program, I assign the input array to the variable ^, its length (i.e. the number of rows) to y, and 0 to x. The value 0 is also left on the stack; during the following loop, it will be replaced by the index of the tallest column.

Within the main loop, ^y(=x= extracts the x-th character of the y-1-th row in ^. This actually returns the ASCII code of the character, so 2% is needed to drop all but the last bit. As a special case, if y equals 0 (which can happen if the tallest column found so far reaches all the way to the top row), the bit looked up will actually come from the last row in the matrix (index -1), but the following y* forces it to zero, thus effectively creating a virtual all-zeros row at the top of the matrix.

The following if will then execute one of the two code blocks preceding it, depending on whether the looked-up bit is non-zero (true) or zero (false). If non-zero, y is decremented by one, and the current value of x replaces the tallest column index on the stack (with the old value temporarily left on top of it). If zero, x is simply incremented by one (and temporarily left on the stack, on top of the tallest column index).

Finally, ^0= extracts the first row of the matrix, , returns its length, and < compares it with the column index temporarily left on the stack (which will equal x if it was just incremented) If the index is less that the length of the row, the loop repeats.

Ps. Based on my testing, it should be possible to shorten this program by one character by replacing the string length test ,< at the end of the loop with >, which cuts the string at the given index and returns the end portion (which will be empty, and thus false, at the end of the loop). However, while cutting a string like that appears to be implemented as a constant-time operation in GolfScript (or, rather, in Ruby, which GolfScript runs on top of), I have not found any official documentation saying so. Just to be safe, I've chosen to feature the slightly longer, but definitely O(1), version above.