You might look into using a shift register or two (595 is popular, there are others) to get your data in/out for the relays and buttons, seeing as you have few data lines left.
Although, I notice you don't note the analog pins (I think) - those pins can be used for digital I/O if you need them...
Other options: using an Arduino Mega (more pins, memory, etc), using a serial LCD display (fewer data lines needed), and of course using another ATMega chip (and doing serial comms between them). ATMega chips aren't expensive, and are easy to set up "standalone" - your only issue might be in finding them for purchase, there was a "shortage" not too long back.