How would I go about getting a small oscillator running at precisely 31,891,269,116 µHz?
Use a 32768kHz crystal like everybody else, but divide by 33669 instead, giving -5.08ppm error. (You can remove that by trimming the loading capacitance if you like).

It's not precise but for a Mars clock it'll be as good as any Earth quartz clock. That is, ignoring the problems of temperature compensation for Mars ambient temperatures, most watch crystals are only available cut for Earth use, unless you can find Martian suppliers...

I'd use the counter-timer peripherals in an MSP430 to do the division, and (assuming you're driving a standard quartz mechanical clock movement) generate bipolar 30ms pulses on its output pins every second, roughly following the original timings which you can measure on an oscilloscope.

Arduino or similar will do the job, but the MSP can be put to sleep between pulses, consuming under 1uA with the LF oscillator running. Here's an example design with source code and PCB for a watch - only Earth time so far, though that can probably be fixed by changing a constant.