First off, there's not much bureaucracy in Iceland, everyone is on a first name basis*. Second, they have known about this problem for centuries, when the soils blew away in the decades after the Vikings first settled the island. Jared Diamond mentions Iceland in his book "Collapse" as an example of success in comparison to the Greenland Norse, who weren't able to adapt and died out. But the way they adapted was to give up having agriculture and by doing other things (a lot of fishing).
Soil restoration is moving about as slowly as reforestation, there still seems to be more short-term profit in cutting down trees and ruining the soil. Although tropical rainforests are vital to the health of the planet, there are interests that can make more money slashing and burning them and putting in a palm oil plantation that doesn't sequester nearly as much carbon. In the long-term view, soil restoration and reforestation can solve the problem of greenhouse gases and global warming, because they both take CO2 out of the atmosphere and forested areas increase cloud cover which counterbalances the warming.
If you want to see a coherent plan (that needs a lot more political support) take a look at
Plan B.
*They don't have last names in Iceland, if the need arises for a second name, they use patronymics (derived from your father's name). This causes all sorts of problems for Icelanders when they travel to a country where 2 names are standard.