AtMega32U4 most certainly doesn’t have the capabilities to handle such displays. 65k colors takes way too much memory. I think even just a few colors would limit the memory available for other data too much. It should be much easier with the chip bateske had beed talking about earlier, Nordic NRF51822, which seems to have 16 or 32 KiB of RAM (and 128 or 256 KiB of flash) compared to current 2.5 KiB of RAM.
Also uses more power, so a bigger battery is used.
We won’t be doing color in the forseeable future. I think I would go with a totally different object before doing color.
We are talking about building an IOT keychain that has a lot of sensors and bluetooth and a display and buttons, etc etc. Think like a mixture of open source Tile / Amazon Dash + Arduboy. With a focus on it’s ability to be used as a mobile 8 bit music tracker. Create little songs on your keychain when you are bored. Use those as ring tone notifications for different events on your phone via bluetooth.
Wait, am I off topic?