You could ditch millis() completely and just set up the timer yourself.
The following code strips away all of millis() and delay(), though it does also stop Tone() and analogWrite() working.
void main(void) {
sei();
setup();
for (;;) loop();
}
void setup(){
}
void loop(){
}