YoungMind.
The eccentricity that you have to worry about is the eccentricity of the total load on your foundation, including the footing selfweight.
Since the applied moment will remain constant, increasing the total vertical load will result in a reduced eccentricity.
As JeddClampett has suggested, it is preferable to keep the resultant load within the 'middle third' of the base. Adhering to that rule would mean that your eccentricity would need to be reduced to 22/6 = 3.7 ft. With an applied moment of 4000 kip.ft, your total load would need to be no less than 1080 kips leading to a footing weight of 1000 kips or so.
Personally, I would not attempt to stay within the middle third, in view of the immense footing that would result.
The other approach is to accept some uplift at the 'rear' of the footing under peak moment conditions, and aim for a larger eccentricity. Just how large is acceptable depends entirely on the permissible bearing pressure under the footing.
As a start point, if you were to assume a final eccentricity of 6 ft, the total load would come down to 4000/6 = 666k, or 566k in the footing itself. Assuming a 22 ft square base, that would work out at 8 ft. thick.
With a linear distribution of bearing pressure and resultant 5 ft from an edge, your bearing pressure diagram would be a wedge, 15 ft long, 22 ft. wide, with maximum pressure = 2*666/(15*22) = 4 kips/sq.ft.
If you can accept more than 4 kips/sq.ft. then you could use a larger eccentricity and a lighter base. A few trials should quickly get you to a reasonable design.
Good luck.