Why XOR and NOT is free in garbled circuit
Regarding the NOT gates in your example. Suppose the wire called $b$ has wire labels $B$ for false and $B \oplus R$ for true. Then you would garble gate "AND1" using these labels as normal, and you would garble gate "OR1" imagining that $B \oplus R$ means false and $B$ means true. 

There are two equivalent ways to think about this. One is to consider the output of the NOT gate to be a separate wire (separate from the input to the NOT gate). If the NOT gate input wire has labels $A, A\oplus R$ then the output wire has labels $A \oplus R, A$.

The other way to think about it is to absorb all NOT gates into their neighboring AND/OR gates. In your example we could garble a NAND for gate AND1 and we could garble a gate $(x,y) \mapsto (\lnot x \lor y)$ for OR1. The way to actually do this is the same as above, just let the garbler switch the "meaning" of the two wire labels, locally for this gate.

Regarding free XOR: the main cost that it saves is not in generating random wire labels for output wires. (In fact, advanced GC constructions do not sample wire labels at random except at the inputs.) The savings are: (1) neither garbler nor evaluator have to evaluate a cryptographic primitive to process this gate. Instead they just make one xor computation. (2) Nothing must be included in the garbled circuit, saving bandwidth. So XOR gates are free for communication cost, and are "free" in computational cost of crypto operations (as you point out, not "free" of all computational cost since some minor xor computation is required).