Since we need a CPU and more to be able to run a Java interpreter and manage a file system that allows you to install apps, you have crossed the line to smart phones in one step.
How else would you run code without a smarter phone?
What I think your real question is what phones allow downloads (be it Java, Brew, Bada or such languages) you might be asking for phones that have downloads but avoid the current scourge of all charges called "the data plan."
But then I would be guessing that was the real question.
Bob
I had a RAZR V3xx and it had awesome support for java games. you could go online and download an game and it would work great. I've had several non-smart phones since and they aren't compatible with anything unless you get it from the service provider.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic