You can't, basically. If someone has implemented the original interface, their code doesn't expose any way of using other operators... so you can't expose the extra method without breaking their code.
One option would be to create a new interface which extended the old one:
public interface IFlexibleEvaluator<T> : IEvaluator<T>
{
bool Evaluate<T>(T key, T value, string operatorVal);
}
Then implementations could add support at their leisure. They could perform the "default to equality" part themselves.