I have read that Assured Shorthold Tenancies of less than 6 months are allowed, but you are not allowed to evict a tenant before 6 months.
That applies only to section 21 ("no fault") evictions. Specifically, according to section 21 of the Housing Act 1988, a notice can't be served in the first 4 months of a tenancy (section 21(4B)), and can't take effect in the first 6 months (section 21(5)).
Section 8 evictions, which require one or more of the reasons listed in Schedule 2 of the Act, do not have this restriction - though only some of them can be used during the fixed term part of the tenancy, and they must be listed in the tenancy agreement in order to be used in that way.
Will I have to wait until he has actually left before I can arrange an AST with new tenants?
Yes, but that's always true. It's very unwise for a new tenancy agreement to be signed until the previous tenants have moved out, because if they don't leave before the new agreement takes effect, the landlord is now committed to finding accommodation for the new tenants.
This is why tenancy agreements are often only signed on the first day of the tenancy.