If you can arrange for all 4 columns to be low, then connect a 4-input AND to the rows and feed that into pin 3 for an interrupt. I believe all the Arduino digital outputs go high-Z state when you go into sleep modes, so you will need extra circuitry to hold the columns low. I think a set of pull down resistors and diodes would be enough to get the right logic level on the keyboard column lines when the AVR is asleep.
When you come out of sleep, you will stop worrying about the AND gate output and disable the circuit that held all the rows low, and go ahead scanning the keys normally.