maximum interrupt-based PWM frequency at 500 Hz
You wrote:


  Using [...] the atmega's hardware pwm is not very suitable because I
  need two 50/50 square waves with a phase difference of pi


I believe hardware PWM is the best solution to your problem. The PWM
outputs can be set to either “inverting” or “non-inverting” mode.
Set the two channels of a single timer to the same duty cycle, with one
in non-inverting mode and the other one in inverting mode, and you have
your complementary outputs.

Example using Timer 1:

const float SIGNAL_FREQUENCY = 24e3;
const uint16_t HALF_PERIOD = round(F_CPU / SIGNAL_FREQUENCY / 2);
const uint16_t PERIOD = 2 * HALF_PERIOD;

int main()
{
    /* Set the PWM pins as outputs. */
    DDRB |= _BV(PB1);  // digital  9 = PB1 = OC1A
    DDRB |= _BV(PB2);  // digital 10 = PB2 = OC1B

    /* Configure Timer 1. */
    ICR1   = PERIOD   - 1;
    OCR1A  = PERIOD/2 - 1;
    OCR1B  = PERIOD/2 - 1;
    TCCR1A = _BV(COM1A1)  // non-inverting PWM on OC1A
           | _BV(COM1B0)  // inverting PWM on OC1B
           | _BV(COM1B1)  // ditto
           | _BV(WGM11);  // mode 14: fast PWM, TOP = ICR1
    TCCR1B = _BV(WGM12)  // ditto
           | _BV(WGM13)  // ditto
           | _BV(CS10);  // clock at F_CPU, start timer
}