In the North of Sweden, above the polar circle on a rafting tour on the Torne river, I was once fed freshly cooked small fishes. The raft captain cut off quite a few branches of birch tree and dipped them into the river. The wet branches were placed on a metal lattice work meant for grilling. On top of this they laid the fishes and on top of the fishes there were new branches of wet birch. The fire had rather high flames when they put the grilling/birch/fish thing on it. After a short while, perhaps 5-7 minutes they flipped the whole thing. This method produced a lovely boiled like fish with a faint taste of smoking. The wet branches of course protected the fish from being burnt and the meal was very quickly prepared. 
Don't you think that paleolithic people could have done the same thing? We also ate smoked reindeer heart. Lovely experience!
The problem is of course that the right we have to roam any countryside does not include the right to cut off trees even if there are many of them. 
Eva