I'm still suggesting lookup tables based on year, not attempting calculations.
(Note that perpetual calendars are relatively more simpler complications to design and make).
So it is possible, but hard to fit into a watchmaking piece!
I could be very wrong about this, but I suspect it might be possible to encode the data optically with much finer resolution and then contrive some kind of daylight driven optical -> mechanical transducer to extract it.
http://www.seikowatches.com/world/technology/spring_drive/
Even the most snardy of mechanical watch enthusiasts agree this is a very beautiful mechanism.