Ideal Shear strength

single crystals with no dislocations are soft and yield readily because there are no dislocations to prevent the movement of newly introduced dislocations. Dislocations are easy to introduce to single crystals from their surfaces. For polycrystals, grain boundaries complicate introduction, but practically dislocations may be introduced through e.g. Frank-Read sources. Dislocations pile up on grain boundaries and other defects, causing strain hardening.
Dislocations allow atoms to move one "row" at a time, rather than requiring the entire plane to move in a coordinated fashion, in a fashion akin to an inchworm. The process of dislocation-based shear deformation is called slip, and the motion of an edge dislocation along an atomic plane is called glide. The required stress for glide is small compared with shearing an entire plane of atoms by several orders of magnitude. Edge dislocations are easy to introduce into a single crystal at the surface, and are the natural mode of shear deformation in metals. As deformation proceeds the dislocations move all the way from one surface to the other. It is impossible to "coerce" a single crystal into deforming without adding dislocations, because dislocations are so energetically easy to add. The question

"How then is a crystal with no dislocations stronger than one with dislocations?"

has a simple answer: dislocation free crystals are not stronger! In fact they are softer and more easily yield to deformation, by virtue of their lack of dislocations.

Instead of a single crystal, assume the material is a practical polycrystal and thus has some obstacles to dislocation motion, such as grain boundaries and volumetric defects. Dislocations are added to internal grains through e.g. Frank-Read sources (Wikipedia), as well as at surface grains by glide. The dislocations will tend to pile up on the obstacles instead of freely moving through the entire crystal. As new dislocations are added, the pile-up gets more severe, until new modes of dislocation motion, which require greater stress, activate, and dislocation motion proceeds again. The overall pile-up process is called strain hardening, and as you noted, is the reason materials with greater dislocation density have higher yield stress than those with low dislocation density.