Spruce was common in Scandinavia.
I remember reading that one reason hops was popular was because it's essentially a weed. And that it outstripped other flavorings not perhaps out of flavor preference, but because it could be grown easily in quantities large enough to flavor beer as it moved from small craft made "home brew" to large urban breweries.