Can I set a random number increment?

Yes, this can be done in System > Configuration > Custom Order Number > Order > Counter Increment Step:

Increment steps can also be customized for invoices, shipping and credit memos.