How does neutralization of free radicals by $\beta$-carotene work?
$\beta$-Carotene is a highly delocalised $\pi$ system. 
According to George Britton there are numerous mechanisms to achieve this. 


Oxidation
Oxidising radicals can remove an electron from the carotene molecule.
$$\ce{CAR + .R+ -&gt; .CAR+ + :\!R}$$
Reduction
Analogous it can accept an additional electron.
$$\ce{CAR + .R- -&gt; .CAR- + R}$$
Hydrogen Abstraction
It is possible to abstract a hydrogen atom from a saturated carbon in allylic position.
$$\ce{H-CAR + .R -&gt; .CAR + HR}$$
Addition
You are correct in assuming, that a free radical may form a bond with that system. This is most common for hydroxyl radicals.
$$\ce{CAR + .OH -&gt; .CAR-OH}$$


You are also correct in assuming, that another radical will always be created. However, the single electron will be very delocalised (resonance stabilised) throughout the whole system and not nearly as reactive as the free radical before.

The remaining molecule can then of course attract more free radicals to form other singlet species, which the body can digest or excrete.