What is the signature scheme with the fastest batch verification protocol for multiple signers? I'm looking for a scheme where signing may be costly (slow) but batch verification with different signers is the fastest possible.

Modified ECDSA allows batch verification for different signers with a 4X speedup [1].

Is there any signature scheme than can do better?

[1] Fast Batch Verification of Multiple Signatures. Jung Hee Cheon and Jeong Hyun Yi
Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA.

The Niederreiter digital signature scheme should also have a very fast verification (but with a mammoth-sized public key); schemes based on Hidden Field Equations (Quartz and Sflash, notably) also offer a fast verification, albeit with a questionable security (the last decade of research on HFE-based schemes has been a long sequence of break-and-repair cycles). NTRUSign is also supposed to be very fast.

Bottom-line is that ECDSA signature verification is quite slow, compared to other signature schemes (it is still fast in practice, because elliptic curves can be optimized in many ways), so there are many signature schemes which will offer faster verification even without batching.



Another kind of batching can be done with ECDSA, when using a binary curve (a curve defined over the $\mathbb{F}_2^m$ field of characteristic 2, for some $m$) and bitslice code: you represent the complete verification process as a circuit of elementary operations on bits (XOR, AND... ECDSA in a binary field is quite appropriate for that); then you use big registers (e.g. 128-bit SSE2 registers) to perform many such computations in parallel, with bitwise operators (when you XOR together two 128-bit registers, you are performing 128 XOR operations in parallel). Writing out such code is difficult, but can offer some impressive speed-ups; see for instance this article (it will still not beat RSA signature verification, though).

Yet another possible ways to speed up ECDSA is by using Koblitz curves (curves in $\mathbb{F}_2^m$ with equation $y^2+xy=x^3+ax^2+1$ where $a$ is $0$ or $1$) which allow for very fast implementations: the doublings in a double-and-add algorithm can be replaced with simple squarings of both coordinates (in mathematical terms, applying the Frobenius endomorphism), something which can be implemented very efficiently. There are some standard Koblitz curves defined by NIST in FIPS 186-3 (the DSA / ECDSA standard), and the whole thing is described in details in the Guide to Elliptic Curve Cryptography (a very good book which I warmly recommend). Combine that with a recent enough x86 CPU with the AES-NI instruction set (not because of the AES things, but for the pcmulqdq instruction for "carryless multiplication"), and you could get some record-breaking ECDSA code which may be competitive even with RSA verification.

So there are many things which can be done with ECDSA; "mathematical" batching is just one of them, and not the one which may yield the biggest speedup in practice.