As far as I understand the order id is autogenerated in database, it is an Identity in Nop_Order table. So the maximum I can do to customise it is to change the seed on the table.
Are there any other options? The request from my client is to have order number available for manual editing. So they can specify any value for it. Maybe it is possible to have a custom field added to order object?