Question: I'm curious about the possibility of sonifying MIDI data, which has a bitrate of 31250. The range of human hearing extends to about 20kHz, which means that the fastest bits of the signal would lie near the top of this range: not ideal for my purposes. I envision stretching the signal, and then passing the result to a small speaker. 

I'm not sure if there is a more precise term for this operation than "stretching" (I'm not super familiar with digital signal processing). At any rate, I can provide a concrete example of what I mean:

00101110100001 >> stretch by 2 >> 0000110011111100110000000011

Not unlikely, the resulting sound will seem be rather atonal/noisy, and that's OK by me. I imagine that I could accomplish this task with Arduino, but I'm wondering about whether this could be done with clever circuit design. For instance, something akin to using a 4018 divide-by-N counter IC? I recognize that the 4018 isn't exactly what I'm looking for, since this acts on a strictly periodic clock signal. 

Any ideas?

Answer: 
Since MIDI data appears to be a series of 8-bit data bytes as sent by a standard UART, you could use a microcontroller to receive the data at the standard MIDI rate, and re-transmit it at a lower baud rate. This assumes that there are sufficient gaps in the data that you won't over-run the receive buffer. 

This would probably require a microcontroller with two UARTs, as the UARTs I've used don't allow different transmit and receive speeds.
How about something like a 4027 JK flip-flop configured to toggle its output (J & K pulled high) ?
This would effective reduce the maximum possible frequency by half.
The result using your example would be:
00101110100001 >> flip-flop >> 00110000111110
Not the same bit-stream by any stretch of the imagination, but I suspect you're not really looking for accuracy here ...