Another idea might be that they have to learn fire from say, studying a flame and learning the properties of it. That way it forces the player to travel to obtain new skills, and you can keep the higher level stuff in areas that are harder to reach.
What would studying entail? I feel like that is the key to making the process more interesting than simply "go to place x and pick up flame y and get skill z."
The actual study would be up to you. It could be as simple as having the player simply wait while the character learns it, to having a mini-game(simple or complex) that can either take the scientific route of putting together atoms or putting together elements, or items, or even just having them actually make fire by somehow making a spark with given items, and getting that spark onto something that will keep flame. Maybe even figuring out what takes the flame best in what situations.