Java - overriding Object's toString() method, but I have to throw exceptions

First, throwing exceptions from toString() is a really bad idea. toString() is used in a lot of system software (e.g. debugger) to generate the representation of the object.

The first preference would be to do something else, maybe create a different method that may throw, and in toString() call that method, catch the exception and produce replacement output such as

super().toString() + " threw " + exception.toString();

If you feel that you really must throw, you can do this:

    try
    {
        str.insert(str.length(), current.element().toString() + " ");
        current = fList.next(current);
    }
    catch(Exception e){
       throw new IllegalStateExcception(super.toString(), e);
    }

This wraps a checked exception (derived from java.lang.Exception) in an unchecked exception (derived from java.lang.RuntimeException). No need to add a throws clause.

Judging by the exceptions, I take it this is the offending line which might throw?:

Position<Entry<E>> current = fList.first();

If that's the case, you can handle that exception. I don't know precisely what fList is and I'm not familiar enough with Java to know if the compiler will be smart enough to know you've checked for it, but logically if the fList could be empty then I would check for that first:

if (/* check for an empty or null fList */) {
    return "";
}
// the rest of your code

If the compiler still doesn't like that, you can take the pretty much the same approach with another try/catch. Something like:

try {
    // the rest of your code
} catch (Exception e) {
    return "";
}

At that point the method really shouldn't be able to throw, since any exception would result in simply returning an empty string. So the header shouldn't need the exception types listed.

As a matter of personal preference I would recommend doing something with the exception when it's caught. At least logging it somewhere, even as a debug log and not necessarily an error. A blanket ignore on all possible exceptions isn't often the best of ideas in the long run.