I don't have a company yet, but without being a registered VAT company, can I invoice a company outside the UK?
Some countries ask for the VAT number every time.
They can ask, but if you do not have one then you do not have one. It is not mandatory for a company to be VAT registered if you are a small company. I think the limit is about 80k a year before you can be registered for VAT.
So yes, you can invoice all over the world without a VAT number.
If you were registered for VAT you would have to charge 20% VAT, and although you can then claim back any VAT you paid on invoices yourself, in the end it is money that you are collecting for the government. Avoid it for as long as you can.