Hi, yes you can start a postdoc without having had your viva. I did this and so did several other people I know.
Tudor, I don't know why they say this, because in reality once you get a post doc they want you to start asap and if you are nowhere near finishing your thesis they will probably give the post to someone who is. For most positions you just need a CV and a cover letter, and it's a standard month until deadline and then month wait to hear back for interview date within a month. This is for biology though - it's obviously different in other fields.
I think when you start applying depends on your financial situation. Ideally, I would have started in between submission and viva and be writing up my papers at the same time. It wasn't fun having to start a postdoc because I needed the cash when I had just finished (not even submitted) my thesis. It then took me a year to write 3 papers in evenings and weekends after work (which to be fair, is still quicker that most).