There is a serial protocol through the dock connector that I've seen documented online. (Haven't looked into it in detail because I haven't had a need to interface with it myself yet.)
There are projects for playing MIDI data via the Arduino. Start looking at those and getting basic MIDI I/O working. Post if you have questions on getting past some particular barrier.
I'm not aware of the iPod sending synchronization data over serial, so you're going to have to make it a WAG as to when it starts. Being that it's based on a hard drive -- and an aging one at that -- the time could start to drift a little longer due to recoverable seek and read errors. I don't think it'll be an exact science. You might get a time display that you can use to trigger when it changes from 0:00 to 0:01 -- that way at least you'll know it's playing.
LCDs are easy. Tons of articles on that, and the hardest part is connecting all the wires. I believe the song metadata is available based on products that use it, but again, I'm not an expert on the iPod serial protocol.