- The world is a sort of medieval era place with very widespread trade, so the character would have access to a range of materials from different climates
- The current colour is a blue-ish hue, but that's definitely not permanent- It could be any unnatural hair colour
- It could be clothing dye or any other sort of material accessible to commoners
Pick your color, if it can dye wool it will dye hair just fine.
Here is a great photo showing a list of known natural dyes, all are possible with medieval technology. several were not available in the real medieval era because they come from the Americas. You can also have things link woad, henna, and saffron for blue, reds, and orange respectively. Keep in mind as hair grow they will have to re-dye periodically no matter what, you can't dye something that does not exist yet. And of course bleaching your hair was a well known technique at the time.
Purity and boldness of color will be affected by cost of course, these would represent the more expensive dyes. keep in mind a commoner probably cannot afford expensive dye so they would be mostly limited to earth tones, nothing unnatural. These would be Henna (red/brown), Madder(red), onionskins (yellow), alderbark (orange), walnut (brown/black)
For an unnatural color at low cost your best bet is green which can be achieved with a variety of homemade dyes, although far fewer than you think. known ways to achieve that are.
Heather and alum
Pivet berries and salt (this can also produce a purplish red so may not be the best choice.)
These are also the ones that are not downright toxic, using lead (black) or lye bleaching were common at the time but were also toxic.
Note also depending on your initial hair color you may have to bleach it before dying, dye can't do much to black hair for instance.
In medieval times dyes could be very expensive for certain tones, while being pretty common and cheap for other.
My grandmother (well past medieval times) used to dye her hair using walnuts and remembered that, while doing laundry with the old method (stacking layers of clothes and ashes, then pouring hot water multiple times), one should be careful to not use the ashes of a certain tree which would have dyed all the laundry with an unwanted color (I am not 100%, but I seem to remember it was rhododendron).
So, some dyes are surely pretty common, but don't expect any flashy or bright color: the reason why purple and red are colors associated with nobility is that in the past they were pretty expensive, so only well off people could afford paying for getting it. Unless your character is rich, they will have to settle for more dull/common ones.