I found a cite for “personal relationship with the Lord Jesus” from the 5 February 1940 New York Times. It’s attributed to Bishop William Manning given in a sermon at the Cathedral of St. John the Divine:
It is the church which brings us into this personal relationship with the Lord Jesus.
The next similar citation in the NYT is by Billy Graham on 15 June 1969:
They’ve been baptized; they’ve been confirmed, but they never had a personal relationship with Christ.
I suspect that if you scour religious, especially evangelical, literature you’ll find many more earlier citations. Don’t confuse the coining of a term with when it enters into the public consciousness. In many cases, terms are around for decades before we notice them, especially when they are part of the jargon of a social subgroup, like this example.