I am trying to set up the free version of Teams (we don't have Office 365) but get the message "Someone has already set up Teams for your organisation. Ask your admin to get you started with Teams, or set up another org in Teams using a different email address." when I try to register.
I am the company IT admin and to the best of my knowlege, we have never registered for Teams before.
Probably by trying to reach MS support and ask to delete your tenant currently associated with your domain (this can be very hard to get to a person who knows about Teams, etc. and to get help while you are not a paying subscriber).
In my experience here in the UK, it is fairly common with the growth of Office 365 for the organisation's domain to be taken (typically companyname.onmicrosoft.com) or for someone in that organisation to have set up a trial at some point in the past and then left the company. This has commonly happened with E3 trials, Power BI trials as Adam and Juan have mentioned, and now free Teams tenants.
There is some recommended options you can pursue
1.) Try to get the login to that tenant which the ex-employee set up. This may not be possible. If you know the onmicrosoft domain (usually companyname.onmicrosoft.com) I have heard of instances of companies reaching out to Microsoft Support and getting access to them but this can take a while as Microsoft needs to verify.
2.) Set up a new tenant. Typically, when the onmicrosoft domain an organisation wants has been taken, for whatever reason, it is easy to set up a new tenant with the onmicrosoft domain companyname365.onmicrosoft.com instead.