Currently I have come to a much more complicated solution than I wished, which completely depends on the automatic grouping behavior (which I temporarily switch on):
SetOptions[EvaluationNotebook[], {CellProlog :> AbortProtect[ Module[{nb = EvaluationNotebook[], evalCell = EvaluationCell[], cells, pos, grouping, groupingRules}, If[CurrentValue[NextCell[], CellGroupingRules] == "OutputGrouping", FrontEndExecute@FrontEnd`NotebookSuspendScreenUpdates[nb]; grouping = CurrentValue[nb, CellGrouping]; groupingRules = CurrentValue[evalCell, CellGroupingRules]; CurrentValue[nb, CellGrouping] = Automatic; CurrentValue[evalCell, CellGroupingRules] = "InputGrouping"; SelectionMove[evalCell, All, CellGroup, AutoScroll -> False]; If[Length[cells = SelectedCells[]] > 1, pos = Position[cells, evalCell]; If[pos =!= {} && pos[[1, 1]] < Length[cells], NotebookDelete[cells[[pos[[1, 1]] + 1 ;;]]]] ]; CurrentValue[evalCell, CellGroupingRules] = groupingRules; CurrentValue[nb, CellGrouping] = grouping; FrontEndExecute@FrontEnd`NotebookResumeScreenUpdates[nb];];]]}] Note that I set CellGrouping to the default Automatic for the EvaluationNotebook[], and CellGroupingRules to the default "InputGrouping" for EvaluationCell[] in order to have it auto-grouped with next output cells (for the cases when automatic grouping is switched off), then I revert the original values of these options back.
Of course such implementation means that will be deleted only cells, which by default are auto-grouped with input cell: manually grouped cells won't be deleted even if they have style "Output" – that is because manual grouping changes the groping behavior by adding the option CellGroupingRules->{"GroupTogetherGrouping", 10000.}. It seems not reasonable to delete manually grouped cells because among them may presetpresent non-output cells, for example "Input" cells and so on. This differs from the standard behavior where all pre-existing output will be deleted on the base of the presence of both CellAutoOverwrite -> True and GeneratedCell -> True options.
Still looking for a better way to do it.
P.S. The whole approach has an issue: by the time the contents of the cell starts executing, the output will already be deleted, and therefore, for example, NextCell[] will return a different value than by default.