You're right that it depends on the song and the musician's level, but a week in advance is my rule, whatever the tunes (usually 2, an A and B). That's usually enough time to learn any gospel tune. If it takes more than a week, than either the musician is not ready skill-wise, or the song is too busy.