I also faced the same problem when i was doing some project , around
an year back & i didn,t found any answer for that, but what i did, i
stored the contents of file  in byte array say 'a', create new byte
array say 'b', which contains the new String at the first and then
append the 'a' to it (but it is very costly (slow) process).
The code looks like this...

I forgot the exact syntax, sorry for that...

byte a[] = fileinputstream.read();//copy the contents of file in a
byte array

byte s[] = "The new String to be added at the top".getBytes();
byte b[] = new byte[s.length()+a.length];
int i = 0;
for(i = 0; i < s.length(); i++){
b[i] = s[i];
}
for(int j = 0; j < a.length(); j++){
b[i+j] = a[i];
}

fileoutputstream.write(b);