Is it possible to construct a fullform trace function

You may use Inactivate to step through the calculation while evaluating in place. Then convert these results into FullForm with HoldForm to prevent evaluation.

First a helper function to evaluate in place.

ClearAll[traceInPlace];
SetAttributes[traceInPlace, {HoldFirst}];
traceInPlace[expr_] :=
 With[{ex = Inactivate[expr]},
  FoldList[
   MapAt[Replace[Inactive -> Identity], #2]@#1 &,
   ex,
   Reverse@Position[ex, Inactive]
   ]]

traceInPlace works like so

traceInPlace[(1 + 2*3)^2] // Column

Then it is only a matter of converting these to FullForm and removing the Inactive heads created by Inactivate.

Activate@HoldForm@FullForm@# & /@ traceInPlace[(1 + 2*3)^2] // Column

Power[Plus[1,Times[2,3]],2]
Power[Plus[1,6],2]
Power[7,2]
49

Each item is wrapped in Hold but if it were not then it would evaluate.

You can also use different forms. For example:

Activate@HoldForm@TraditionalForm@# & /@ traceInPlace[(1 + 2*3)^2] // Column

Hope this helps.

Update: Thanks to @jjc385 for suggesting HoldForm instead of Hold. Change made above.

ff = FullForm /@ Trace[Power[Plus[1, Times[2, 3]], 2], TraceOriginal -> True];

sf = ToString /@ ff;

Fold[StringDelete[#1, #2] &, sf, {"HoldForm[", "]," ~~ EndOfString}]

{Power[Plus[1, Times[2, 3]], 2]],
 List[Power]], List[Plus[1, Times[2, 3]]], List[Plus]],
   List[1]], List[Times[2, 3]], List[Times]], List[2]], List[3]],
   Times[2, 3]], 6]], Plus[1, 6]], 7]], List[2]], Power[7, 2]], 49]}

Still a lot of junk in there, and no clear way to parse it to get the OP's requirement ...

Power[Plus[1,Times[2,3]],2] 
Power[Plus[1,6],2] 
Power[7,2] 
49

Here's one way.

Find the depth of the expression and evaluate parts level by level.

ex = Hold[(1 + 2*3)^2];
f[expr_] := 
 Replace[FullForm[expr], x_ :> With[{eval = x}, eval /; True], {#}] & /@ 
  Range[Depth[expr], 2, -1]

f[ex] // Column

Hold[Power[Plus[1,Times[2,3]],2]]
Hold[Power[Plus[1,6],2]]
Hold[Power[7,2]]
Hold[49]

For more information on the evaluation, please check this and this.