In the UK, the government is made up of politicians from the political party (or sometimes parties) who are able to form a working majority in the House of Commons (the elected house in UK governance). They are the entity that sets the agenda for making any new laws, changing any old laws, setting out the budget, etc. - i.e. they "run the country".
If you are out of government, it means that you are not part of running the country. This most commonly means that you hold elected office (i.e. are an MP), but are not part of the ruling party. It also mean that you hold elected office, are part of the ruling party, but have not been given a ministerial position (i.e. you don't run, or help run, any office of the state. These MPs are known as "backbench MPs" or "backbenchers"). The least common usage (in my experience), and the one described in Tᴚoɯɐuo's answer, is for describing the time before they became an elected politician, or for describing a time when they took a break from politics.
I suspect that the quote is referring to the time that David Davis was a backbencher (note that you can be a backbencher for the opposition too).