The first one will use 5 numbers for the time, and 1 number plus a few 3mm LEDs for the track. The LEDs will light up to count the tens. The idea is rvdammit's, and I think it will work quite well.
The second one will use three of the dual-14-segment displays. Normally, it will display the time (hh:mm:ss), but if a new track starts, it can display something like 'Tr ##' or something like that. I can also scroll the album or file name across the display, say once every minute or so. Much more versatile, but more work.
It turns out that those alphanumeric displays are the exact same displays as greatbiggary bought some time ago, and using his handy interactive Flash pinout schematic (scroll down to the bottom of the page), I can easily determine which segments need to light up for which character.
Driving them is actually not very hard, when using a shift register. I connected the ground-pins of the two halves of the first character to the collector of a transistor, with the emitter connected to the ground. I use a pin to allow current to pass through this transistor -- with that setup, I can multiplex the halves.
So, it's simply clocking in a half of a character, opening the transistor (and closing the other one), wait for a bit, clock in the other half and open the other transistor. With only a few modifications to my 7-segment driving source, I could show an 'A' on a display!
Now, the real challenge is to let this be driven by input from the RS232-port, and to have some sort of sensible scrolling mechanism for when the texts are larger than 6 characters. But the first step is set!