Okay, I've got a thought here, but it's still all theory. The Ringwraith's steads could be the
missing link in our mystery. So here it is.
There would definately have been many unknown creatures across Arda(like down south where Ungoliant is from, for example). There could have been strange giant reptilian beings in the world. Morgoth took some of them and used his power to inhibit them with fell spirits and to change them physically. Slowly, dragons developed, with fire-breath and cool spell casting eyes. Later wings were added.
Then there are the Nazgul's rides. Sauron, being a good little minion, tried to copy his master's brilliance. Only he could not get that fire thing down, or find the necessary spirits to give them power. So he just threw the wreched critturs to his best followers to play with. And they used them well.
As I said, this is still theory, but its my best guess.
As far as breeding goes, well, I don't really care except it was nearly non-existant