There appears to be no practical solution to this problem. For some reason, when legend is placed outside, the InnerPosition property of uiaxes includes the space taken by the legend itself (instead of the strict plot-box, labels excluded). Thus, one cannot manipulate the plot-box dimensions independently of the legend. As far as I can tell, this is a MATLAB limitation.
P.S. As a work-around, one can place the text in the legend as a title, and then fix the axes dimensions (Position property). Clearly, this only works if you have a single Line in a plot (or, to be more precise, a single Line for which you actually care of having a legend associated with it), but since this was my case, it is a fine work-around.