Do airlines have to get permission from the FAA if they want to change their livery?
Not the FAA, but the manufacturer.

If the parts are composite, only a small range of colors may be approved, depending on the glass transition temperature of the resin matrix. For gliders, only white is allowed for most of the surface area, and similarly composite parts of airliners must be painted in a light color so they don't heat up too much in sunlight. Curiously, the lower surface has the most restrictions, because here the reflected light from a concrete surface and the restricted ventilation create the highest surface temperatures.

Next, the UV absorption capability, moisture protection characteristics and the chemical stability of the paint when in contact with aviation fuel, hydraulic fluids, de-icing fluids and other solvents is important. Composite gliders must use a special topcoat which is more brittle than the composite structure, so cracks will show up. Airliners may use more flexible paints, but must then undergo regular inspections of their composite parts.

Metal surfaces are less demanding and can be painted in any color. Only the area in front of the windshield should be dark enough to reduce glare and irritating reflections.