1) any host that uses Cpanel will have access to Interchange for shoping cart software. Or you can install a wonderful free shopping cart suite yourself called OSCommerce which is php/mysql based and very full featured.
2) This might cause you some problems, but is not impossible to find. Keep in mind that this doesn't necessarily have to come from a host. You can sign up for processing with 2checkout, ematic, or Paysystems, just to name a few.
3) Pretty much any host should be able to offer this without any problem.