Solution:

If $A$ and $B$ are at the greatest distance, then they must be vertices. For suppose $A$ is not a vertex. Then there is a segment $XY$ entirely contained in the polyhedron with $A$ as an interior point. But now at least one of angles $BAX$, $BAY$ must be at least $90^{\circ}$. Suppose it is $BAX$. Then $BX$ is longer than $BA$. Contradiction.

Take a plane through $A$ perpendicular to the line $AB$. Then the polyhedron must lie entirely on one side of the plane, for if $Z$ lay on the opposite side to $B$, then $BZ$ would be longer than $BA$. Now move the plane slightly towards $B$ keeping it perpendicular to $AB$. The intersection of the plane and the polyhedron must be a small polygon. The polygon must have at least $3$ vertices, each of which must lie on an edge of the polyhedron starting at $A$. Select three of these edges.

As the plane is moved further towards $B$, the selected vertices may sometimes split into multiple vertices or they may sometimes coalesce. In the former case, just choose one of the daughter vertices. In the latter case, let $O$ be the point of intersection of the plane and $AB$. Let $O'$ be the point of intersection at the last coalescence (or $A$ if there was none). Then we have three paths along edges, with no edges in common, each of which projects onto $O'O$ and hence has length at least $O'O$. Now select one or more new vertices to replace any lost through coalescence and repeat.