How long before PhD graduation should I start applying for post-doc positions? My earliest PhD graduation date is 10 months away. Funding permits me to stay 1–3 months longer, so the final date is still uncertain.

It is never too early to make contacts for possible post-docs. But how long in advance is too early to formally apply to post-doc job openings or funding opportunities? Depending on the bureaucracy, the path from applying to starting can probably be anything from a week up to a year — someone I know is applying with ESA which had the opening advertised in August, application deadline in October, will have interviews in December/January, and the commencement of work only in September, 13 months after the initial job advertisement. My personal guess is that the long time between interviews and starting is to create a level playing field between those who do and those who don't need to go through a visa application procedure.

If I'm too early in applying for a post-doc, a hosting institution might prefer someone who can start earlier and where the graduation date is more certain. For example, in my case the graduation date is still uncertain, so there is a risk in accepting even if they are willing to wait. Project funding might also require the money to be spent rather soon.

If I wait too long, there might be a considerable period where I'm between jobs. Having a long (>6 months) period between jobs is a disadvantage for me. Maybe it's also a disadvantage for a hosting institution (I'm not sure).

How do I find the balance? For example, considering the duration of funding and visa applications, does it make sense to apply e.g. 8 months in advance? Or is it in any case virtually inevitable to have at least several months before my PhD graduation and the start of a post-doc?
It depends on the type of funding associated with the postdoc position: 

1) If the funding is already there and has a limited duration (for instance a one-year funding within a one-year research project), then indeed, the recruiter might not want to wait 10 months for you, since it would mean that an important part of the funding might be "wasted". 

2) If the funding is already there, but can be used later on (for instance a one-year funding within a five-year research project), then it could be possible to start only in 10 months. 

3) If there is no funding yet, and you need to get it yourself, then you have to start as early as possible, since it can take a long time for the whole process to finish. 

Note that case 3 is usually a process you started with a potential advisor, rather than answer to a particular announcement. In any case, it's always a good thing to informally contact potential advisors directly to see about the specificity of a particular position.