The quote you are looking for is:
...if words spoken of old be true, not by the hand of man shall he fall, and hidden from the Wise is the doom that awaits him. However that may be, the Captain of Despair does not press forward, yet. He rules rather according to the wisdom that you have just spoken, from the rear, driving his slaves in madness on before.
My Answer:
It seems that Gandalf at least has enough confidence in his abilities to fight the Witch King one on one. The "prophecy" itself is fairly vague, and there are numerous examples of "man" in the book referring both to a "male" and to "someone who is of man kind". It is difficult to say with certainty that the prophecy could or couldn't have been fulfilled by Gandalf, but my inclination is to believe that it could have been.
Edit: Note too that the words are "the hand of man" and not "the hand of a man". Man when used in the first sense usually refers to mankind.
Gandalf is a Maia, so not a "man", and was sent to Middle Earth to fight Sauron. The wizards were prevented from matching their power with Sauron directly, but it is indicated that they could have fought Sauron themselves. Someone who could do that should have the power to destroy the Witch King, Sauron's agent and lesser.
Additionally there are "prophesies" that do not come true in the books as well, so to set much store in them isn't necessarily wise. (For example Theoden says, much like this prophecy; "no living man shall pass" the Paths of the Dead, yet Aragorn disproves that).
Finally, the prophecy states that "not by the hand of man shall he fall", which to me indicates that it is a foregone conclusion how the Witch King shall fall. It seems different from "no man can kill him" in that it doesn't state that it isn't possible, just that that isn't how it will happen. Kind of like saying; "I shall drive my car home now". I could walk, but that isn't going to happen.
Note: Everything below here is simply evidence for my summary above.
Here is a quote indicating Gandalf believes that he can fight the Witch King:
In rode the Lord of the Nazgûl. A great black shape against the fires beyond he
loomed up, grown to a vast menace of despair. In rode the Lord of the Nazgûl, under the archway that no enemy ever yet had passed, and all fled before his face. All save one. There waiting, silent and still in the space before the Gate, sat Gandalf upon Shadowfax: Shadowfax who alone among the free horses of the earth
endured the terror, unmoving, steadfast as a graven image in Rath Dínen.
'You cannot enter here,' said Gandalf, and the huge shadow halted. 'Go back to
the abyss prepared for you! Go back! Fall into the nothingness that awaits you and
your Master. Go!'
The Rohirrim arrive before any battle can take place however, and the Witch King "...left the Gate and vanished."
Gandalf then means to follow/hinder him:
Gandalf looked through the gaping Gate, and already on the fields he heard the
gathering sound of battle. He clenched his hand. 'I must go,' he said. 'The Black
Rider is abroad, and he will yet bring ruin on us. I have no time.'
but Pippin asks him if he can save Faramir from his father, to which he responds:
'Maybe I can,' said Gandalf, 'but if I do, then others will die, I fear. Well, I must come, since no other help can reach him. But evil and sorrow will come of this. Even in the heart of our stronghold the Enemy has power to strike us: for his will it is that is at work.'
It seems that Gandalf realizes that he is needed on the battlefield, and his fears are realized when Theoden dies. Gandalf certainly felt that he could help, whether it be by killing the Witch King or by driving him off it is uncertain.
Further evidence to Gandalf's apparent ability to match the Witch King in a battle: (emphasis mine)
'Yet now under the Lord of Barad-dur the most fell of all his captains is already
master of your outer walls,' said Gandalf. 'King of Angmar long ago, Sorcerer,
Ringwraith, Lord of the Nazgûl, a spear of terror in the hand of Sauron, shadow of
despair.'
'Then, Mithrandir, you had a foe to match you,' said Denethor. 'For myself, I have long known who is the chief captain of the hosts of the Dark Tower. Is this all that you have returned to say? Or can it be that you have withdrawn because you are overmatched?'
To which Gandalf responds
'It might be so,' Gandalf answered softly. 'But our trial of strength is
not yet come...'