I think it should be possible to replant trees by just planting the coresponding seeds into the soil. And the skill should be cheap or better yet there from the beginning.
It should have a low success chance and the quality can't be raised, only retained. Only the farming skill and the seed quality should have an effect on the resulting tree, with the quality hard capped with farming.
Reason:
When newbies settle, they need a metric ass-ton of wood.
Houses, palisades, buckets, barrels, boats, carts, ...
And wood is also needed for herbalist tables, which are needed to plant trees right now.
I don't think we have so few trees in densely habitated areas because of griefers, but because it's a PITA generally to replant them and you need to fell some first before you can begin with replanting.
Of course trees should also regrow naturally, but it shouldn't be so fast, that humans aren't necessary anymore.
I strongly believe, that newbies should be able to do something constructive from the start. And there are not many things more constructive in this game than replanting trees!