Genre is not inherently supported on MusicBrainz, though you might be able to get something from the tags. Year is easier, and earliest year is actually pretty simple here (look at the table of this recording, for instance), but you'll run into issues where people have added the same recording as five separate entitles (when they should be merged) and where separate versions of a song -- radio edits and re-recordings, obviously, but sometimes even mono vs stereo -- are also separated (actually desired for the database, but potentially not for your list). Either way, your best hope for the year would probably be some script querying the web service using variables it pulls from each line of the file, but I wouldn't know how to get that working.
By the way, Picard's lookup works perfectly well without CDs, as long as you can give it music files (MP3, WAV, OGG, ...). Still sounds like it won't work in your situation, but thought I'd mention it just in case.
