An account number implies sparseness and diversity so that a valid account number cannot be easily guessed, so yes sequence numbers will definitely not work.
Random numbers would be perfect for you use, provided you take samples from a pool that is much larger than the number of users you expect to have. Elementary statistics will tell you the probability of a duplicate everytime you search for a new number.
You can use the standard mod-10 number verification that is used by most credit cards. It won't prevent the user from making up invalid account numbers, but will reduce the chance of someone typing in an incorrect one.