Boosters were in use by 21 August 1957, the first successful suborbital launch of the R-7.
Definition of 'booster':
A booster rocket (or engine) is either the first stage of a multistage launch vehicle, or else a shorter-burning rocket used in parallel with longer-burning sustainer rockets to augment the space vehicle's takeoff thrust and payload capability.
The term "Strap-on booster" is somewhat ambiguous. Literally, it means the booster is attached to the rocket via straps. I don't know any boosters that are attached like that: they are usually attached via fittings that are part of the booster's structure, and not a separate band that runs around the booster's body.
Some people use "strap-on booster" as a synonym for "booster", but that's pointless.
Strap-on boosters are, in my opinion, a subclass: this refers to boosters that are optional, i.e. the core stage can be launched either without or with boosters.
Some notable rockets that used strap-on boosters:
- Titan 3, first launch of a Titan 3C with boosters was in 1965.
- Ariane 3, first launch in 1984.
- Delta 2, first launch 1989.
From this list, I'd say the Titan 3 is the first operational rocket to use strap-on boosters.