The question is not whether all men require grace to seek God, the question is whether an unregenerate man can do good or seek God. And the answer is YES.
The Philipian jailer sought God. Did he receive grace? We aren't told, but it is safe to assume he had prior knowledge of Paul and Silas and their doctrine. He may have heard them preach or heard of miracles they performed. And the great earthquake that opened their cells doubtless convinced him they were men of God. So this is grace.
But was he regenerate when he burst in and asked how to be saved? NO. And we know this because they told him he must believe on Jesus to be saved.
And until you believe on Jesus you can not possibly be regenerate, cannot possibly have spiritual life because you are dead in trespasses and sins.
An unregenerate man cannot believe without God's grace, but with God's grace he can.
But no man is regenerate until after he believes.
Does Christ commit Himself to all who believe in HIS name?
No, in John 2:23-25 Jesus rejects the belief (will) of these people. (BTW the word believe in vs. 23 same word in John 3:16.) they displayed belief, but it was rejected by JESUS. (ESV) 23 Now when he was in Jerusalem at the Passover Feast,
many believed in his name when they saw the signs that he was doing. 24
But Jesus on his part did not entrust himself to them, because he knew all people 25 and needed no one to bear witness about man, for he himself knew what was in man.
One then should, and rightly so, ask the question what belief/or faith is accepted by Christ and when does He accept faith.
Enter John 3.
Jesus converses with a learned teacher of Israel, Nicodemus. This Teacher explains his position, ie. belief in Jesus, "we know(statement of belief) that you are a teacher come from God".
Nicodemus is by sheer human reasoning deducing this knowledge. If then faith (ie. we know) precedes regeneration then Jesus should have congratulated this wise teacher.
But notice the response of Jesus to Nicodemus' knowledge/assent.
3 Jesus answered him, "Truly, truly, I say to you, unless one is born again
(can also be rendered born from above) he cannot see the kingdom of God."
Jesus says to Nicodemus no matter how much human reasoning you apply to your soul's salvation the first thing that must happen, you must be born from above.
Now Nic did not understand.
Jesus explains, That which is born of the flesh is flesh, and that which is born of the Spirit is spirit.
This is two distinct births. First birth is only flesh. The second or new birth is spirit from The Spirit.
The ability of The Spirit in contrast to the flesh, in spiritual matters, is detailed by Paul in 1 Corinthians 2:13,14
13 And we impart this in words not taught
by human wisdom but taught by the Spirit, interpreting spiritual truths to those who are spiritual.
14 The natural person does not accept the things of the Spirit of God, for they are folly to him, and he is not able to understand them because they are spiritually discerned.
Now notice the knowledge of those who experience this New Birth or birth from above.
Jesus uses the
illustration of the wind.
Do not marvel that I said to you, 'You must be born again.' 8 The wind blows where it wishes, and you hear its sound,
but you do not know where it comes from or where it goes. So it is with everyone who is born of the Spirit."
What a tremendous truth,
you do not know you are born again until after you are born again.
This requires then that regeneration (new birth) precede faith.
Why?
Because if the opposite were true then
faith would demand "the wind" or The Spirit to blow or work right here. This would violate the unknown work of The Spirit that Jesus clearly sets forth to Nicodemus and us in John 3:1-8.
BTW after the unknown work of The Spirit is begun, through the new birth, faith can be placed, hence Jesus further explaination to Nicodemus in John 3:10-21.