OK. TN and H1B are totally different.

1. Can I get a new TN if my H1B application is approved before Oct. 1?

Yes. You can apply TN at border as long as you have never filed I-485 before.

2. Can I change my status from H4 to TN?

You can apply the TN status if you get a job offer from a US company.

3. Can I change H1B to TN if the next company doesn't want having transfering H1B?

Like the above questions. Yes.

4. How long will take to change TN to H4?

If you apply H4 at border, you'll get it immediately.

5. Should both of us cancel H1B application for the flexibility? (No GC)

Don't quite understand your question. TN status has to be renewed annually while H1B is a three-year team. It is up to you.