It is not possible for an object to be in the shadow of Earth permanently - although it could be in the semi-shadow called penumbra, the full shadow (umbra) does not extend that far. There is a special place called the L2 Lagrange point that allows an object to orbit around the Earth at about the same rate as the Earth orbits around the Sun - thus always remaining in the same relative place in terms of shadow.
However, L2 is not a super stable point to orbit in, and thus objects tend to fall away. This is not a problem for artificial satellites, though, and the James Webb Space Telescope, when launched, will take advantage of this constant half-shadow to make better celestial observations.
So:
Yes, it is possible, although unlikely. This "moon" is more like the Death Star, and will need some kind of course correction to stay in orbit. This could potentially be "explained" by matching the moon diameter and the umbra diameter, meaning if it started to move out of position the sun would warm part of the surface, leading to off-gassing pushing the moon back into place. Probably not 100% scientifically valid, but otherwise this needs to be a spaceship, not a moon.
To calculate the L2 point: $$d_{Earth-L2} = d_{Earth-Sun}\sqrt[3]{\frac {M_{Earth}}{3M_{Sun}}}$$ Where $d$ is respective distance, and $M$ is the respective mass. Note the cube root.
To calculate the Umbra Diameter at the L2 point:- First calculate the umbral distance: $$d_{umbra}= \frac{d_{Earth-Sun}}{\frac{r_{Sun}}{r_{Earth}} - 1}$$ Where $r$ is the respective radius of the body.
- Then, if the umbra distance is more than the L2 distance, you can calculate the size of the umbra (max size of your moon) with this equation:
$$r_{umbra}=\frac{r_{Earth}}{\frac{d_{umbra}}{d_{umbra}-d_{Earth-L2}} + 1}$$
For the non-mathematically-inclined, I combined this all into a Google Spreadsheet, make a personal copy to edit.
So, the Lagrange point kind of orbits both.
Normal densities (3,000-8,000 kg/m^3) should work. Mass of the object at the L2 point does not matter significantly. However, some kind of automatic correction will be necessary.