DEMs and Hillshades are two different things. DEMs are surfaces with elevation information. Hillshades are a visual representation of a shaded relief and the values are not dependent on the elevation itself but of the aspect and angle illumination, as you noticed from 0 to 254.
If you'd like to represent a map with elevation data but using the visualization of the hillshade, you should display both layers, DEM on top with transparency (looks nicer if you also add some transparency in your hillshade, just play a little bit until you find what suits you best) and just add the legend displaying the colors and values of your DEM (there's some preset elevation color ramps in ArcGIS).
You can also do this in 3D. In ArcScene. Double click your layer and in the "Base Heights" tab choose "Floating from custom surface" and add here your DEM path.