During power down, could I attach 4-input AND gate to the rows? This would give logic low if any key is pressed? When controller is put into sleep, do the output columns that have been set to zero hold? Or do they become floating?

4-input and gate would be a continuous power consumption.

During power down, port pins retain the status. The best solution is to use a key which has 3 points. One for column, one for row and the third is common for all keys. So if you set columns at zero and scan rows, then you can use this third pin to interrupt the CPU. It will act as an AND gate.

Or alternatively you can use Idle mode instead of power down. Use a timer to interrupt the CPU at every, say , 50 msec. Upon interrupt, you can check the status of the keypad. Although not as much power saving as that of power down mode, but just an alternative.