I'm thinking of using an ATTiny13/85/44 but I haven't chosen which yet as I have not got much into the project beyond an idea.
I am thinking of a code entry keypad where I enter a 4-digit number onto a keypad that if it's correct causes a solenoid to unlock a door. I can hard-code the number into the software but I want to be able to change that number. How do I do that part, particularly since the device will be powered off when not in use.
Store the PIN in EEPROM…
Using a switch on the secure side of the lock, enable entry of a new PIN.
That way, only someone with legitimate access can change the code.
You can make it more secure with additional tricks, but that should get you started.
I would use FRAM, the write and read is at processor and basically unlimited read and writes. 32Kx8 less then a pack of cigarettes.
You need a 4x3 Keypad (Fig-1) which requires 7 IO lines. So, choice could be 14-pin ATtiny44 AVR with 4 KB flash, 256 B RAM, 256 B EEPROM, and 12 IO lines.
You install ATTinyCore and program it using IDE and Arduino as ISP.
Figure-1:
For something that only will be changed once in a while?
But more than just the internal EEPROM 
Nope. I put different value resistors on each key and read it via the ADC.