Writing half-reaction for the oxidation of iron (III) hydroxide

Here is the unbalanced equation.

$$\ce{Fe(OH)2_{(s)} + O2_{(g)} -> Fe(OH)3_{(s)}}$$

Therefore, one half-reaction is

$$\ce{Fe(OH)2_{(s)} + O2_{(g)} -> Fe(OH)3_{(s)}}$$

and the other half-reaction is

$$\ce{O2_{(g)} -> 2H2O_{(l)}}$$

My question, how are we justified in making the latter half-reaction?

Oxygen should not be in both half reactions. You'll get yourself in trouble.

Try:

$$\ce{Fe(OH)2 ->Fe(OH)3}$$ $$\ce{O2 -> H2O}$$

We are justified in making the latter half reaction because balancing the first half reaction will likely require water added to the reactant side to help balance the $\ce{H}$ and $\ce{O}$ atoms.

However, an equally appropriate second half reaction might be $$\ce{O2 -> OH-}$$ noting that there is an extra hydroxide in the products of your overall redox reaction.

I would simplify the oxidation reaction further, ignoring the hydroxide ions which do not really participate:

$\ce{Fe^{2+}->Fe^{3+}}$

The reduction of oxygen makes the extra hydroxide in the iron(III) hydroxide product, but it needs water to provide the (protic) hydrogen, thus:

$\ce{O2 + H2O->OH^-}$

You can balance the half-reactions and then the (net ionic) full reaction from there.