Es gibt ATMegas mit PCINTxx -Eingängen.
Die sind wie geschaffen für Dein Problem.