How can magnets be used to pick up pieces of metal when the force from a magnetic field does no work?

The Lorentz force $\textbf{F}=q\textbf{v}\times\textbf{B}$ never does work on the particle with charge $q$. This is not the same thing as saying that the magnetic field never does work. The issue is that not every system can be correctly described as a single isolated point charge

For example, a magnetic field does work on a dipole when the dipole's orientation changes. A nonuniform magnetic field can also do work on a dipole. For example, suppose that an electron, with magnetic dipole moment $\textbf{m}$ oriented along the $z$ axis, is released at rest in a nonuniform magnetic field having a nonvanishing $\partial B_z/\partial z$. Then the electron feels a force $F_z=\pm |\textbf{m}| \partial B_z/\partial z$. This force accelerates the electron from rest, giving it kinetic energy; it does work on the electron. For more detail on this scenario, see this question.

You can also have composite (non-fundamental) systems in which the parts interact through other types of forces. For example, when a current-carrying wire passes through a magnetic field, the field does work on the wire as a whole, but the field doesn't do work on the electrons.

When we say "the field does work on the wire," that statement is open to some interpretation because the wire is composite rather than fundamental. Work is defined as a mechanical transfer of energy, where "mechanical" is meant to distinguish an energy transfer through a macroscopically measurable force from an energy transfer at the microscopic scale, as in heat conduction, which is not considered a form of work. In the example of the wire, any macroscopic measurement will confirm that the field makes a force on the wire, and the force has a component parallel to the motion of the wire. Since work is defined operationally in purely macroscopic terms, the field is definitely doing work on the wire. However, at the microscopic scale, what is happening is that the field is exerting a force on the electrons, which the electrons then transmit through electrical forces to the bulk matter of the wire. So as viewed at the macroscopic level (which is the level at which mechanical work is defined), the work is done by the magnetic field, but at the microscopic level it's done by an electrical interaction.

It's a similar but more complicated situation when you use a magnet to pick up a paperclip; the magnet does work on the paperclip in the sense that the macroscopically observable force has a component in the direction of the motion of the paperclip.

Although what Ben and others have said might be sufficient, I would like to state my point.

Consider a piece of conductor being lifted up by the magnetic force. The current is towards the right(with velocity $w$), and the magnetic field is going into the page. Hence, the magnetic force is upwards. Now, as the conductor moves up, it gains a velocity $u$ in the upward direction. Hence the magnetic force changes direction as shown in the figure, but the upward component remains the same.

Now, observe that the horizontal component of the magnetic force is acting against the current. To maintain the current, the battery responsible for the current does work against this force and is the source of work done.

A popular analogue in Classical Mechanics is that of the role of normal force in pushing a block upwards a slope. The normal force does no work but is required to move the block up the slope. It's role is simply to redirect $F_{mop}$ in the upward direction. This is exactly the role of magnetic force in lifting stuff.$

Source of Images and Knowledge:Griffiths' Introduction to Electrodynamics

The Lorentz force is the only force on a classical charged point particle (charge $q$ - see Ben Crowell's answer about nonclassical particles with fundamental magnetic moment such as the electron). The magnetic component of the Lorentz force $q \mathbf{v} \wedge \mathbf{B}$, as you know, is always at right angles to the velocity $\mathbf{v}$, so there is no work done "directly" by a magnetic field $\mathbf{B}$ on this charged particle.

However, it is highly misleading to say that the magnetic field cannot do work at all because:

1. A time varying magnetic field always begets an electric field which can do work on a classical point charge - you can't separate the electric and magnetic field from this standpoint. "Doing work" is about making a change on a system, and "drawing work from a system" is about letting the system change so that it can work on you. So we're always talking about a dynamic field in talking about energy transfer and in this situation you must think of the electromagnetic field as a unified whole. This is part of the meaning of the curl Maxwell equations (Faraday's and Ampère's laws). Moreover, once things (i.e. charges and current elements) get moving, it becomes easier sometimes to think about forces from reference frames stationary with respect to them: Lorentz transformations then "mix" electric and magnetic fields in a fundamental way.
2. A classical point charge belonging to a composite system (such as a "classical" electron in a metal lattice in a wire) acted on by the magnetic field through $q \mathbf{v} \wedge \mathbf{B}$ thrusts sideways on the wire (actually it shifts sideways a little until the charge imbalance arising from its displacement begets an electric field to support it in the lattice against the magnetic field's thrust). The magnetic field does not speed the charge up, so it does not work on the charge directly, but the sideways thrust imparted through the charge can do work on the surrounding lattice. Current elements not aligned to the magnetic field have torques on them through the same mechanism and these torques can do work. These mechanisms underly electric motors.
3. Another way to summarise statements 1. and 2. is (as discussed in more detail below) that magnetic field has energy density $\frac{|\mathbf{B}|^2}{2\mu_0}$. To tap the energy in this field, you must let the magnetic field dwindle with time, and electric field arising from the time varying magnetic field can work on charges to retrieve the work stored in the magnetic field.
4. The thinking of current elements shrunken down to infinitesimal sizes is a classical motivation for thinking about the interaction between magnetic fields and the nonclassical particles with fundamental magnetic moments, as in Ben Crowell's answer (I say a motivation because if you go too far classically with this one you have to think of electrons as spread out charges spinning so swiftly that their outsides would be at greater than light speed - an idea that put Wolfgang Pauli into quite a spin).

We can put most of the mechanisms discussed in statements 1. and 2. into symbols: suppose we wish to set up a system of currents of current density $\mathbf{J}$ in perfect conductors (so that there is no ohmic loss). Around the currents, there is a magnetic field; if we wish to increase the currents, we will cause a time variation in this magnetic field, whence an electric field $\mathbf{E}$ that pushes back on our currents. So in the dynamic period when our current changes, to keep the current increasing we must do work per unit volume on the currents at a rate of $\mathrm{d}_t w = -\mathbf{J} \cdot \mathbf{E}$.

However, we can rewrite our current system $\mathbf{J}$ with the help of Ampère's law:

$\mathrm{d}_t w = -\mathbf{J} \cdot \mathbf{E} = -(\nabla \wedge \mathbf{H}) \cdot \mathbf{E} + \epsilon_0 \mathbf{E} \cdot \partial_t \mathbf{E}$

then with the help of the standard identity $\nabla \cdot (\mathbf{E} \wedge \mathbf{H})=(\nabla \wedge \mathbf{E})\cdot\mathbf{H} - (\nabla \wedge \mathbf{H})\cdot\mathbf{E}$ we can write:

$\mathrm{d}_t w = -(\nabla \wedge \mathbf{E}) \cdot \mathbf{H} + \nabla \cdot (\mathbf{E} \wedge \mathbf{H})+\partial_t\left(\frac{1}{2}\epsilon_0 |\mathbf{E}|^2\right)$

and then with the help of Faraday's law:

$\mathrm{d}_t w = +\mu_0 \mathbf{H} \cdot \partial_t \mathbf{H} + \nabla \cdot (\mathbf{E} \wedge \mathbf{H})+\frac{1}{2}\epsilon_0 |\mathbf{E}|^2 = + \nabla \cdot (\mathbf{E} \wedge \mathbf{H})+ \partial_t\left(\frac{1}{2}\epsilon_0 |\mathbf{E}|^2+\frac{1}{2}\mu_0 |\mathbf{H}|^2\right)$

and lastly if we integrate this per volume expression over a volume $V$ that includes all of our system of currents:

$\mathrm{d}_t W = \mathrm{d}_t \int_V\left(\frac{1}{2}\epsilon_0 |\mathbf{E}|^2+\frac{1}{2}\mu_0 |\mathbf{H}|^2\right)\,\mathrm{d}\,V + \oint_{\partial V} (\mathbf{E} \wedge \mathbf{H}).\hat{\mathbf{n}} \,\mathrm{d}\,S$

(the volume integral becomes a surface integral by dint of the Gauss divergence theorem). For many fields, particularly quasi-static ones, as $V$ gets very big, the Poynting vector ($\mathbf{E} \wedge \mathbf{H}$ - which represents radiation), integrated over $\partial V$ is negligible, which leads us to the idea that the store of our work is the volume integral of $\frac{1}{2}\epsilon_0 |\mathbf{E}|^2+\frac{1}{2}\mu_0 |\mathbf{H}|^2$, so the magnetic field contributes to the stored work. It should be clear that this discussion is a general description of any dynamic electromagnetic situation and is wholly independent of the sign of $\mathrm{d}_t W$. So it applies equally whether we are working through the currents on the field or the field is working on us.

The above is very general: we can bring it into sharper focus with a specific example where it is almost wholly the magnetic field storing and doing work: say we have a sheet current circulating around in a solenoid shape so that there is a near-uniform magnetic field inside. For a solenoid of radius $r$, the flux through the solenoid is $\pi r^2 |\mathbf{B}|$ and the magnetic induction if the sheet current density is $\sigma$ amperes for each metre of solenoid is $|\mathbf{B}| = \mu_0 \sigma$. If we raise the current density, there is a back EMF (transient electric field) around the surface current which we must work against and the work done per unit length of the solenoid is:

$\mathrm{d}_t W = \sigma \pi r^2 \mathrm{d}_t |\mathbf{B}| = \frac{1}{2} \mu_0 \pi r^2 \mathrm{d}_t \sigma^2 = \pi r^2 \times \mathrm{d}_t \frac{|\mathbf{B}|^2}{2 \mu_0}$

This all assumes the rate of change is such that the wavelength is much, much larger than $r$. So now, the energy store is purely magnetic field: the electric field energy density $\frac{1}{2}\epsilon_0 |\mathbf{E}|^2$ is negligible for this example, as is the contribution from the Poynting vector (take the volume $V$ in the above argument to be a cylindrical surface just outside the solenoid: just outside the solenoid, the magnetic field vanishes and the Poynting vectors are radial at the ends of the cylinder so they don't contribute either. The above analysis works in reverse: if we let the currents run down, the electromagnetic field can work of the currents and thus the stored magnetic energy can be retrieved.