Is it legal is make a full time fireman work an average of 56 hours
per week and not pay them overtime?  I read the Fair Labor Standards
Act and it seems that anything over 40 hours in a fixed seven day
period constitutes overtime.  The Valley View City web page says that
they will get overtime for over 159 hours in a 21 day period, so this
would mean the firemen are non-exempt, but it appears the 21 day
period might be illegal when reading the FLSA.

Here is the Webpage:
http://www.valleyview.net/building/240.doc

Section 240-10
240.10	COMPENSATION AND OVERTIME.
(a)	Full-time firefighters shall be compensated as provided for from
time to time by Council.
(Adopting Ordinance)

(b)	Overtime for all full-time firefighters, with the exception of the
Fire Chief, shall be paid at the rate of an additional fifty percent
of the employee's regular hourly rate of pay for any hours worked
beyond 159 hours in any twenty-one day work period.  Full-time
firefighters shall work an average of fifty-six hours per week. 
Overtime compensation earned will be paid no later than the second
succeeding pay period from which it is earned.
(Ord. 94-6-8.  Passed 6-7-94.)

I have a feeling I am missing something somewhere that states
emergency personnel are exempt some/all FLSA regulations or something.
 Any help will be appreciated.

This is merely a comment, not by any means an answer. Firemen are paid
overtime, under FLSA. Just not 16 hours of OT per week. Schedules vary
by department: 1 on, 2 off; 1 on, 1 off for x days, then y days off,
etc. But generally, not just a straight M-F 56 hours in a week. That
would result in 112 hours in two weeks - some two week periods we work
96 hours, some 130, again, depending on how the days fall in the pay
period. So, for example, Las Vegas pays us FLSA overtime of 28 hours 5
times a year. And overtime for extra days worked, and holdover is
extra and not included in FLSA.