There are a few points to consider here:
As soon as someone accepts a job offer they have a contract with their employer. An employment contract doesn’t have to be written down.
Accepting a contract
As soon as someone accepts a job offer they have a contract with their employer. An employment contract doesn’t have to be written down.
source: https://www.gov.uk/employment-contracts-and-conditions/overview
What is a contract of employment
There is always a contract between an employee and employer. You may not have anything in writing, but a contract will still exist. This is because your agreement to work for your employer and your employer’s agreement to pay you for your work forms a contract. Your employer does have to give you a written statement within two months of you starting work. The statement must contain certain terms and conditions.
source: https://www.citizensadvice.org.uk/work/rights-at-work/basic-rights-and-contracts/contracts-of-employment/#h-what-is-a-contract-of-employment
From what you put in your question you are a step ahead from this as you have a written offer and have given written acceptance of that offer. So it sounds like you already have a valid employment contract with your new employer (enforcing it, if they try to withdraw, is another matter)
Several people in the comments seem to be hung up on the fact that you (and they) haven't signed anything, but this doesn't seem to be relevant.
A contract does not have to be partly or wholly in writing for it to exist, although having it in writing obviously provides more certainty as to what the parties agreed.
Following on from this, a contract of employment does not need to be signed for it to be a binding agreement between the parties as acceptance of its terms can be either verbal or implied through conduct.
Source: http://www.thisismoney.co.uk/money/experts/article-2715470/Is-employment-contract-binding-I-never-actually-signed-It-says-I-three-month-notice-period-never-signed-I-respect-it.html
UK Employment Law Myth (4): Employees must sign their contract for its terms to apply
if an employee does not sign his or her contract, this does not mean that the terms in that contract do not apply. An employer cannot cite an employee’s failure to sign and return the contract as meaning that the terms are not binding and therefore it can change those terms or deprive the employee of rights under the agreement. Likewise, employees cannot argue that the fact they never signed their contract means that they do not have to carry out duties under it.
source: http://www.xperthr.co.uk/blogs/employment-intelligence/2013/08/uk-employment-law-myth-4-employees-must-sign-their-contract-for-its-terms-to-apply/
[To be fair this causes a lot of confusion for the British public. For example when you park in a private car park with clearly posted terms and conditions you are entering a contract with the car park, so break their terms and they can invoice you (with something that looks like a fine but legally is an invoice you agreed to pay.) The typical response is but i didn't sign anything
which isn't a valid excuse.]
Additionally, this article (http://www.personneltoday.com/hr/ever-late-withdraw-job-offer/) discusses withdrawing offers from an employers POV (written by a 'senior associate lawyer'), it states if the offer is withdrawn after being accepted they could end up owing you payment for your notice period (enforcing this is, again, another matter)
You must get a ‘written statement of employment particulars’ if their employment contract lasts at least a month or more, within 2 months of the start of employment.
https://www.gov.uk/employment-contracts-and-conditions/written-statement-of-employment-particulars
So it's not wrong to not have a signed contract before you start work, although I'd treat it as odd.
You seem particularly worried that you may be left without a job, this isn't an unusual worry but you probably have less rights that you imagine:
- Your new employer can probably get rid of you within your probationary period if they want anyway (depending on your contract and conditions)
- Even if you are unfairly dismissed then you can't go to an employment tribunal until you have worked there for two years anyway.
(https://www.gov.uk/dismissal/what-to-do-if-youre-dismissed)
All that being said, it does sound rather odd the way your new employer is behaving. It sounds to me like they don't understand the norms (or even the law) surrounding employment, which might be enough to make you think twice.
It might be worth organizing your thoughts and having a frank discussion with your new employer, setting out your concerns and asking them to allay them. If they can't do so, or reacts badly to you raising these valid concerns then I'd consider walking away.
I am not a lawyer, but have linked to authoritative sources (UK Govt, Citizens Advice and actual lawyers)