First way is without algebra.
Second way is using algebra.

First way:
They'll have to average 1/4th of 496 which is 124.

So get the two odd numbers just below 124 and the two odd numbers
just above 124 and you have them:

121 + 123 + 125 + 127 = 496.

But your teacher won't allow that method because it doesn't use 
algebra.

Using algebra

first odd integer = n
second odd integer = n+2
third odd integer = n+4
fourth odd integer = n+6

n + n+2 + n+4 + n+6 = 496
              4n+12 = 496
                 4n = 484
                  n = 121

So they are  

first odd integer = n = 121
second odd integer = n+2 = 121+2 = 123
third odd integer = n+4 = 121+4 = 125
fourth odd integer = n+6 = 121+6 = 127

Edwin