Read the iPhone contract, this has been discussed over and over. Even if you removed the data plan many times, the fact that you are still using an IMEI number that is iPhone, they will keep adding the data plan back on. AT&T is not stupid, and yes data plan is REQUIRED for iPhone 3G.
And yes, they can legally do it, read your contract.