I don't believe there is any method to dynamically choose the color when using Excel's built in Conditional Formatting. You could, as you guessed, use some VBA to accomplish though.
Assuming Column C has the lower date in the range range, Column D has the upper date in the range, Column E contains a colorindex (see here), and Column F has the date we are testing (and this is the cell we are coloring) you can create the following subroutine:
Public Sub update_colors()
Dim rngDates As Range
Set rngDates = Sheet1.Range("F2:F3")
Dim rngDateCell As Range
For Each rngDateCell In rngDates.Cells
If Sheet1.Cells(rngDateCell.Row, 3).Value <= rngDateCell.Value And Sheet1.Cells(rngDateCell.Row, 4).Value >= rngDateCell.Value Then
rngDateCell.Interior.ColorIndex = Sheet1.Cells(rngDateCell.Row, 5).Value
End If
Next rngDateCell
End Sub
Set F2:F3 in the third line to the entire range of dates in your worksheet.
You can kick off this subrouting/udf with a button. On your developer tab (go here for instructions on how to enable it, if you haven't already) Click "Insert" and choose the button under "Form Controls". Draw the button somewhere on the sheet (you can move it afterwards), and choose the subroutine you just created from the list. Now when you click the button, the subroutine will run.
If you don't like the colors, you can use something besides .interior.colorindex() to set the cell color. I'm a big fan .Interior.Color = RGB(,,) You would need to have the RGB values in the sheet somewhere to pull that off, but you will have millions of colors to choose from instead of just the 56 that colorindex allows.