Emacs with ido or helm does this [1] but unfortunately it requires quite a bit of customisation, and even more customisation to get nice fuzzy matching.

It does include every possible command though, and it can show keyboard shortcuts.

[1]: http://sachachua.com/blog/2014/03/emacs-basics-call-commands...