Since your record length is not fixed you are going to end up using a RandomAccessFile to make use of the index - it is the only way to jump to a record start.
Off the top of my head I would say that you will have to scan the file looking for the starts of lines, for each line start record the file position and grab the content you are going to sort on - sounds like a job for a custom object containing two variables:
long fposition ;
String key ;
store those guys in a collection - maybe a TreeMap - when your scan is done, the TreeMap will have the sorted order and the fposition will point to the line start so you can do a RAF seek to it.
Bill