The Nazgul were sorcerers
Men proved easier to ensnare. Those who used the Nine Rings became mighty in their day, kings, sorcerers, and warriors of old. They obtained glory and great wealth, yet it turned to their undoing. They had, as it seemed, unending life, yet life became unendurable to them. They could walk, if they would, unseen by all eyes in this world beneath the sun, and they could see things in worlds invisible to mortal men; but too often they beheld only the phantoms and delusions of Sauron.
"Of the Rings of Power and the Third Age", published in The Silmarillion
In The Lord of the Rings: A Reader's Companion, Hammond and Scull explain the use of the word "witch" to just mean a person who does magic, not specifically a female.
The use of witch in his title seems odd to contemporary eyes, to whom the word is popularly associated only with females, but its oldest use recorded in the Oxford English Dictionary is ‘a man who practises witchcraft or magic; a magician, sorcerer, wizard’, and for most of its history it belonged to no gender.
The Lord of the Rings: A Reader's Companion - Prologue
As for actual examples of him doing magic, note that flaming lightsaber from the movie actually is in the book. He doesn't break Gandalf's staff though.
The Black Rider flung back his hood, and behold! he had a kingly crown; and yet upon no head visible was it set. The red fires shone between it and the mantled shoulders vast and dark. From a mouth unseen there came a deadly laughter.
‘Old fool!’ he said. ‘Old fool! This is my hour. Do you not know Death when you see it? Die now and curse in vain!’ And with that he lifted high his sword and flames ran down the blade.
The Lord of the Rings - Chapter 4 - "The Siege of Gondor"
Also see Matt Gutting's answer about the gates.