drive 3 phase induction motor with only DC (not pwm) thru each phase
Yes, using square waves instead of sine waves can be done.  As you suspected, it will be less efficient.  Think of it in frequency space.  The fundamental component of the square wave will do all the work.  The remaining harmonics will heat the motor without adding useful torque, will add mechanical stresses, and can cause more audible noise.

You say you can't get a PWM frequency fast enough to produce a reasonable sine wave, but that is hard to believe.  Surely the AVR can do 25 kHz or so PWM?  I have done this a few times with Microchip PICs, some of which even have a special PWM module intended for this application.