Do airlines have to get permission from the FAA to change their livery? It would be great if someone can throw in some examples where this has happened.
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.
In general, the aircraft owners can paint the aircraft whichever the way they want. However, changing of aircraft liveries comes under refinishing of decorative coatings has to be done by certified personnel as it is considered major maintenance. The materials used should comply to the applicable safety regulations.
A short answer, but: No
They can paint their planes pretty much however they want. I imagine various agencies and their customers would have something to say about it if they did something outrageous, but they can repaint their planes without asking permission or even informing the FAA.