I use Gimme Some Tune on the Mac and as my music is playing from iTunes it runs a search and adds the lyrics and artwork automatically to each song file.
i'm pretty sure this work on more than just 1.1.3 firmware...i know it works on 1.1.4 obviously, i have 1.1.4 and lyrics. i'm almost positive it should work with older firmware versions as well...this was included on my 3rd gen video ipod which came out way before the iphone did, i'd assume they would put this in the initial release
then again, they didn't put a LOT into the initial release as far as technology that's been around awhile *cough*mms*cough* lol