While I doubt this because of the precedent it would create...
I see no reason why it wouldn't be feasible.
Walmart as a lone retailer for an inexpensive iPhone is like having a 900lb. gorilla in the room with an iPhone sandwich board. I could see as a business opportunity having Walmart conjoin with Apple for a specific, low end, product. Instant ka-ching!
The 4GB iPhone is awesome. Wish I had one. Bet a lot of people do. So there are giant sized products out there for $500? So what. Most people probably never will use all 4GB unless they cling to masses of video. 3 GB of audio is practically endless, and if you work it with iTunes it's all you ever need.