Another obvious idea would be to give extra score points to the weaker player. Keep track of the score differences from each game and you can adjust the handicap based on the recent average score difference, so the handicap points naturally decrease as the margin of skill decreases between the players.
I've never seen a skill spread that big where the stronger could consistently wipe the weaker totally off the board, but if you've seen it, then I agree the point handicap probably won't be appropriate for such a case.
That would require a lot of games. The variance in points difference is quite high and a slightly stronger player can often win by an arbitrarily large margin.
An obvious point to start would be the LittleGolem database of ranked games. I imagine it would be possible to automate the determination of the points difference, even though that is not recorded in the regular statistics that you get after each match.