Assume for the rest of my answer that, unless otherwise stated, the material in question is a macroscopic single crystal of some metallic element, free of volumetric defects (e.g. carbides, graphite, etc).
Summary: 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.
Theoretical Single Crystal Strength
There are two modes possible modes of plastic deformation in tension: cleavage and shear. Cleavage is movement of two portions of the crystal toward either the tension directions, away from the cleavage plane. Shear is movement of two portions of the crystal at an angle with respect to the tension directions, along a shear plane. Shear is more likely because atomic bonds do not need to be fully broken. Instead they can hop to their neighbors as shear progresses.
Due to Polyani and Orowan, the theoretical cleavage stress is
$$
\sigma_{\textrm{max}} \approx \frac{E}{\pi}
$$
which for most metals centers around $50\ \textrm{GPa}$. The experimentally determined yield strengths of the strongest steels push just past $1\ \textrm{GPa}$ for comparison, and most metals are closer to $0.1\ \textrm{GPa}$.
Due to Frenkel, the theoretical shear stress is due to an entire plane of atoms hopping over a neighboring plane such that each atom moves by one atomic spacing to a new spot. The required stress is given by
$$
\tau_{\textrm{max}} \approx \frac{G}{5.13}
$$
and because $\nu\approx 1/3$
$$
G = \frac{E}{2\left(1+\nu\right)}
\approx \frac{3E}{8}
$$
so that
$$
\tau_{\textrm{max}} \approx 0.073E
$$
which for most metals centers around $5\ \textrm{GPa}$, which is closer to the experimental values and smaller than the cleavage strength by an order of magnitude.
Practical Single Crystal Strength
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.
Reference
Most of this answer comes from a lecture module at University of Alabama in PDF format, located here. Primary sources for the equations are:
M. Polyani, Z. Phys. v. 7 (1921) p. 323
E. Orowan, Rep. Prog. Phys., v. 12 (1949) p. 185
J. Frenkel, Z. Phys. v. 37 (1926) p. 572
but good luck locating copies.
Much more information on dislocations can be found at University of Cambridge DoITPoMS here.
