re: dyeing, VT makes a spray vinyl dye that works on interior plastics too. Basically dye and strong solvent to get it to sink in a little. Used that to do repairs and custom work on dashboards when I was doing stereo stuff.

 

The most cost effective would be to wrap it. It’s not a huge focal point of the car and since your going darker its unlikely anyone would even notice it. It also would give you a plethora of colors to choose from so you could probably get it to blend in well with your new headliner.