Playing Melody with Tone() without using delay()
As others have noted, this can be done using the same method as used in the standard 'BlinkWithoutDelay' example sketch, and combining that with a state-machine type approach. In a simple state machine you'd assume you can be in one of two states: outputting a tone, and not outputting a tone.

Applying these ideas to your code snippet above:

// BEFORE SETUP
const int tonePin = 8;
unsigned long previousMillis = 0;
const long interval = pauseBetweenNotes;
const long interval = noteDuration;
boolean outputTone = false;                // Records current state


// IN LOOP
unsigned long currentMillis = millis();

if (outputTone) {
// We are currently outputting a tone
// Check if it's been long enough and turn off if so
    if (currentMillis - previousMillis &gt;= noteDuration) {
        previousMillis = currentMillis;
        noTone(tonePin);
        outputTone = false;
    }
} else {
// We are currently in a pause
// Check if it's been long enough and turn on if so
    if (currentMillis - previousMillis &gt;= pauseBetweenNotes) {
        previousMillis = currentMillis;
        tone(tonePin, melody[thisNote]);
        outputTone = true;
    }
}