Do any of the major credit cards generally accepted by internet
vendors (I guess Visa, Diners) offer a service equivalent to American
Express' "Private Payments" service where you can get a one-time card
number that can't be rebilled or otherwise used fraudulently?

In addition to American Express' Private Payments service, Discover
offers a program called "Discover Deskshop" which can generate
single-use card numbers:
http://www2.discovercard.com/deskshop/main.shtml

Unlike American Express and Discover, which issue their own credit
cards, Visa and Mastercard cards are issued by participating banks,
not the Visa or Mastercard associations.

Citibank is the only Visa/Mastercard issuer I could locate that offers
a single-use card number program, called "Virtual Account Numbers":
http://www.citibank.com/us/cards/tour/cb/shp_van.htm

This page at Bankrate.com has a quick overview of these three programs:
http://www.bankrate.com/brm/news/cc/20021011b.asp

Search terms: "citibank virtual account numbers"

Thanks - Great answer!

MBNA also offers a similar feature for their cards, it is called
ShopSafe and can be accessed from http://www.mbnanetaccess.com, if you
have an account with them.

Both MBNA and Citibank allows you to set an expiration date and a
credit limit. MBNA, Citibank and Discover permit only one merchant to
use the generated card number. Sometimes this causes problems when
initial payment is done by one merchant, but a subsequent payment is
processed with a slightly different spelling of merchant's name.

Discover does not allow you to set a limit or expiration date, instead
the generated card number is linked to your original card, which may
be more convenient for recurrent payments.

For all three companies a single use card number can be generated off
their web sites, or you can install small applications to your
desktop.