This is an interesting project. Have you checked out ExpressionLineDiff in the Wolfram Function Repository? You may be able to get some ideas from it.
From example 7 it looks like you are representing diffs in the head as a list of diffs. Perhaps these could be represented using position 0 in ReplacePart:
ReplacePart[0 -> g][f[x, y]]
g[x, y]
Replacing the whole expression can also be done with ReplacePart:
ReplacePart[{{}} -> y][x]
y
