I became Muslim last year while I was legally separated from my (non-Muslim) husband. Our legal divorce is mutual and still being processed. Does that prohibit me from getting a Nikah done with a Muslim man?
In Islam a separation does not equal a divorce (similar in other religions). So you are legally married and you cannot be married to more than one person - legally or religiously.
Once you are divorced, you may then marry a Muslim man.
In Islam the "legal marriage" has little consequence, it is done for practical reasons. The "nikah" (marriage contract) is all that is required.
In most Muslim countries, the Nikah is the same as a legal marriage - that is, the Nikah document is your marriage certificate.
However in other countries you can get a legal marriage (also called a court marriage, civil marriage), and the religious one. In this case, as far as Islam is concerned, only the Nikah is binding. So if you both signed the Nikah you are now husband and wife, even if you did your civil/legal marriage at a later date.
Well from a shari'a point of view you are legally divorced because: You separated from your husband and you converted to Islam and afterwards at least one waiting period has passed. This would mean from this point of view you are free for marriage!
But as you seem to live in a non-Muslim country it would be the best to have at least a document which clearly shows you and your husband are separated of course a divorce document would be better in any case! You will know your Ex-Husband better but you might have to be aware that a Nikah could mean that the divorce process would have some changing lines which could end against you!
Also read the fatwa #114722 on islamqa.
And Allah knows best!