Is it possible to colour areas between (vector) contours without making it a DEM first?
Joshdoe seems to have done so in Create filled contour map with GRASS but does not say how.
You can simply convert the lines to polygons under Vector > Geometry Tools > Lines to Polygons. Then symbolize your polygons accordingly. As whuber stated in a comment to your question this will only work if your contours close in on themselves with no dangles as shown in your example.
In principle, you cannot do this in a unique, accurate way without reconstructing something like the original DEM.
Let's see why, by doing the computation with a (difficult but realistic) example. It begins with a small portion of a 30 meter DEM, about 15 by 11 kilometers.
Contours have been computed at regular intervals: this is where you begin.
To perform the fill, we need to (1) identify the regions between contours and convert them to polygonal (or raster) features suitable for filling and (2) find the elevations of all contours bounding each region. Although this can be done entirely with vector operations, that would take some intermediate-level programming and is much trickier than it might seem. A raster solution, on the other hand, is relatively easy.
To obtain the regions between the contours, convert the contours to a grid format, construct the indicator grid of the NoData values, and extract its morphological components (aka "RegionGroup").
The purple regions are the gaps between contours.
Each region has been given a separate identifier and colored with a random color.
Returning to the contours, compute their Euclidean allocation grid. The value at each cell is the value of the contour closest to it.
This image is zoomed into the top center of the previous ones to show detail. The contour lines are superimposed to show the relationship between the Euclidean allocation values and the nearest contours.
Finally, a zonal summary of the Euclidean allocation values, using the regions as zones, captures all the needed information: everything that can possibly be calculated without recreating a DEM is contained in this summary.
The original hillshaded DEM shows in the margins beneath a choropleth map of the zonal minimum within each region (that is, the value of the lowest contour bounding each region). The contour lines are drawn on top for reference.
Success! The regions between the contour lines have all been filled according to the values of their bounding contours. So where are the alleged problems? Let's look at the zonal statistics table. This one has been sorted by decreasing area so we can focus first on the largest regions between the contours.
See that range of zero in the fourth line? It is a large region which is bounded only by contours at 300 (meter) elevations. Let's highlight it in the map:
Most likely this region contains elevations between 200 and 300 meters, but the lower 200 meter contour does not appear anywhere on the map. (This particular region appears to be near the head of a valley which extends to the west off the map.) Because of this, the only contours with which it is in contact are at 300 meters. Now, how is the software supposed to be able to tell whether this is the upper contour or the lower one? The answer--which you have already determined visually--is that you must somehow extrapolate the elevation values downward from the peaks, across the 300 meter contour, and into lower levels. Doing that requires knowing how topography actually behaves and amounts to estimating elevation values in the between-contour regions. That means you have to recreate the DEM! (At least in a semi-quantitative manner: your extrapolation can be crude, provided it's in the right direction. For instance, if you happened also to have a layer of point elevations, with at least one point within each problem region, you could use that (via a spatial join) to classify every region accurately.) Without this additional calculation of elevations, it is not possible to determine whether this region should be classified as being between 200-300 meters or 300-400 meters.
How common is this problem? It occurs along all the edges as well as within any peak and any valley:
In other words, it will always occur somewhere in a contour map.
I suppose you could go through and manually assign values to the problem regions according to your visual assessment of the map, but in most cases it would be easier, faster, and more reliable simply to create a DEM--even a crude one will do--and use that to classify and symbolize the regions.
All the calculations performed to make these illustrations can be carried out exactly as described, step-for-step, in QGIS/GRASS, ArcGIS/Spatial Analyst, and most other raster-based GISes. For details, see the help pages for your favorite GIS.