"A man" means one man. Without "a", it means man as in the whole population. To me, it doesn't make sense without the "a". "Man" without any articles means the same thing as "mankind".
Originally, there was no article, however. The words were:
"That's one small step for man, one giant leap for mankind."
However, according to the transcript, "a" was meant to be said. That is the source of confusion.
This article and this article explain the dropping of "a". Here is the transcript.
Historical accuracy aside, it makes the most sense with "a".