I'm developing an app that works on iOS 5 and it appears that Xcode automatically says "iOS 4.3 or newer". Can I still (in 2012!) create apps that work on iOS 3.x?
Many people have iPhone 3G or even the original iPhone, and these are so old that it's not wise to run newer iOS versions than 3.x on them. These people would be excluded from getting the app, which is a pity.
If my app doesn't use any features that an iPhone 3G with iOS 3.1.3 wouldn't have, can I publish the app to require "iOS 3.1 or newer"?
Yes, you can. But you certainly don't have to. The people who are not on at least iOS 4.0 are under 3% based on the usage statistics I'm seen. I wouldn't worry about it too much.
"can I publish the app to require "iOS 3.1 or newer"?" Yes.