It is very unusual in my experience for a company (at least not a small company) to begin the on-boarding procedures and schedule a start date without a signed offer letter. While this wouldn't be a contract, it is your official signal to them that you are committed to joining their organization and accepted the terms of their offer. But it wouldn't be out of the question they they took your verbal acceptance at that signal of commitment.
The fact that they gave you a start date and started a background check indicates to me that they think you have accepted, even if you don't think you accepted anything.
On the company's side, this likely means that they have informed the other potential candidates that they have filled the position, and the manager has begun whatever processes are needed to get your started (ordering equipment, getting accounts set up, etc).
Since there appears to be no real legally enforceable contract based on your description, you aren't committed to anything. You can walk away without fear of legal repercussions. However, you will likely burn your bridges with company A and it would be a surprise if they ever considered you for another position in the future.
Depending on the industry and what the competition is like, you would be surprised who you run into in the future, and who will remember your name. You may even encounter Company A as a client, or someone from Company A in a management role of another company you wish to work with.
So the decision should come down to two questions...
- "Is this job with Company B, both in the short term and in the long term, worth ruining my reputation with Company A"*.
- Will I ever need Company A in the future for a job, or a client".
If you can answer those questions, it should help you make your decision.