A passport is a document attesting to both the holder's identity and nationality. Since the requirements for identification (name, photograph, birthdate, signature, etc.) have been internationally standardized for some time, I would say the usefulness of the passport will be governed by the usefulness of holding a particular nationality. Your passport will only be accepted by as valid by countries which recognize your government. Therefore, the fewer countries your state is recognized by, the less useful your passport is.
The answer cannot therefore be Taiwan or Israel, as a holder of one of their passports can still enter many other countries. I would venture to say the least useful passport is that of Somaliland. Somaliland is a de facto independent country; while it is nominally part of Somalia, it has functioned as a separate state for two decades. However, no other country recognizes it, and no other country will accept a Somalilan passport. A similar situation exists for several post-Soviet states which are only recognized by certain other post-Soviet states and/or by Russia, and others like Western Sahara and Northern Cyprus.
Among states with wider recognition, I would rank the passports least useful to a traveler are those for which it is most difficult to obtain an exit visa. After all, even if another country will give you or waive an entry visa, it does you no good if you cannot get out. I can think of no more extreme case than the DPRK (North Korea), whose government is recognized by nearly every other UN member, but from which it is almost impossible to leave if not on official state business. The many crossing the border into China are not exactly collecting entry stamps at the airport.
I don't think the other "freedom of movement" rankings are relevant to this specific question, as they are rankings of the number of countries where visa-free travel is possible. In relative terms, a passport holder who can never even apply for a visa is in a far worse situation than someone who must apply for one (and in some cases, visas are available upon arrival for a nominal fee, not much more effort than visa-free travel), hence why a North Korean passport is less useful than an Iraqi or Afghan passport.