Scandinavia didn't have the social stability to "convert" as a unit any earlier. The all-at-once adoption of Christianity around the 1000s went hand in hand with the consolidation of the kings' power.
So you'd need the people, in small, local communities, to decide that Christianity was best. This happened in Ireland. Maybe an Irish-inspired monastic movement? Maybe Irish missionaries go to Scandinavia way back in the 8th century?
Celtic Christianity in Scandinavia. I like it. Maybe not the likeliest thing to happen, but I like it.