Как его зовут?

I believe его is needed. Without it I think you're asking literaly "How called?" It's like asking "Whats name?" I may be wrong so feel free to correct me.

[edit] I just saw the part about you're trying to say "What's the name", not "What's his name". That still means it should be "Как зовут", not "Что зовут".