What would you guys do

Have a look at SimpleTimer and Timer libraries:
http://arduino.cc/playground/Code/SimpleTimer
http://arduino.cc/playground/Code/Timer

They do the same thing as the underlying code in the BlinkWithoutDelay sketch but
are implemented as libraries and use configurable c++ objects so they are much easier to use IMHO.

--- bill