Mit deiner ersten Vermutung hast du Recht. Du schreibst das Programm auf einen Speicher(beim AVR ist es Flash) und der Mikrocontroller führt das dann aus. Dafür hat er entsprechende Logik eingebaut.
Das andere gibts allerdings auch, nennt sich programmierbare Logik, Vertreter davon wären CPLD und FPGA.