Short Answer
Normal maps and Normals are two different things: Normals are a geometric property of any mesh/surface its use is not exclusive for shading and lighting calculations but have actually many other uses for example in physics. Normal maps are textures that encode alternative normal vectors used in computer graphics to simulate bumps.
Long Answer
Normals in geometry a normal is a vector or a line that is perpendicular to a given object (e.g. plane normal, vertex normal ). Normals in graphics are usually used for light calculations, such as calculating Diffuse reflection across a surface by taking the dot product between the light direction and surface normals. Normals are usually calculated based on the geometrical properties of the mesh (Faces/Vertices), by taking the cross product of any two non-parallel edges that lies on the same plane.
In OpenGL normals are specified per vertex (hence called vertex attributes) even though they might be calculated only for each face in this case you need to specifiy the same normal for each vertex in a face. Normals can be interpolated by OpenGL across each vertex of a face(triangle) so you can calculate the reflected light per pixel not per vertex, hence giving a more accurate result.
Normal Mapping: on the other hand is a technique in computer graphics that encodes Normals in a texture map, so each normal is encoded per texel. It is usually used for faking the lighting of bumps and dents (e.g. bump mapping, parallax mapping).
Since normals are calculated based on the geometrical properties of the mesh/surface, Normal Maps will give you alternative Normals that can simulate the bumps to add detail to the surface without adding more polygons.
Normal maps are usually generated using a much more detailed 3D model, then calculating the normals based on this model and encoding it in a Normal Map.
Why do we need both?
Well talking only about rendering, normals and normal maps are usually used together to achieve the final lighting effect, a good example might be a bump shader, where you need the normals map normal to achieve the bump lighting effect, and you will still need the geometric normal to calculate what is called the tangent space. Tangent space is usually used to provide re-usability for normal maps.
Keep in mind that a normal is considered a geometrical attribute of the surface and has many more uses than only light calculations. Normal maps on the other hand are usually used for superficial effects.
Extending the answer to explain why tangent spaces are important:
Short answer:
Tangent spaces are used to make normal maps independent of the underlying geometry.
[EDIT] Added Image to represent normal map in tangent space and normal map in world space.
Long answer:
The below picture shows the UV plane and the normal that defines the tangent space, when generating a normal map we will already know that the used space will always have the Normal pointing in the Z direction (that's why normal maps look bluish), this will help us ignore the surface curvature**, .
Tangent space gives us the advantage that our normal maps encoding isn't bound to a specific mesh normals. Suppose we encode our normal map in world or object space, then each normal we encode will have a direction based on how the original mesh normals vary in world space, not to mention your normal map will be affected by the model transformations.
In the above two pictures it's pretty clear that tangents space makes normal maps(right), independent of the underlying geometry because all normals are encoded in almost the same direction with small variation to simulate the effect of the bumps.
**surface curvature is defined by the amount which a geometric object deviates from being flat, or straight in the case of a line but this is defined in different ways depending on the context.
