It sounds like a fairly simple problem, and the non-blocking approach you're taking is the right way to go. You're also on the right lines implementing each feature in a separate function.
I suggest you define the variables used by each algorithm as static variables within the function. For example, here is a minimal blink function:
static const int LED_PIN = 13;
static const unsigned long BLINK_INTERVAL = 500; // duration of each blink phase
static unsigned long lastBlinkTime = 0;
if(millis() - lastBlinkTime >= BLINK_INTERVAL)
lastBlinkTime += BLINK_INTERVAL
In your case instead of just blinking the LED on and off you will be fading it, but the same general approach will work. Instead of just inverting the LED state each time, you would need to have a variable recording the current analogWrite value and the direction of the current fade (i.er. getting brighter or dimmer). This would be very similar to the blink example - add the current direction to the brightness, if it becomes negative or greater than 255 then invert the direction, constrain the brightness to be 0 .. 255 and apply it to the LED. The fade speed and smoothness are determined by the interval between brightness changes, and the magnitude of the change.
For the fade in / hold / fade out / hold you will need a simple state machine with a state for each of those steps. Again, the sdtate variable could be a local static. A switch/case statement is a very convenient way to implement simple state machines like this.
The really nice thing about this non-blocking approach is that you can implement all these function independently and just call whichever ones you want to use - so you can start your sketch with a few copies of blink at different frequencies and then make some of them more elaborate.
By the way, note that the timing in that example is slightly different to your code - the difference is subtle, but if you use subtraction the code will handle timer rollover correctly whereas your original code doesn't.