Except for the backup requirements, the Gemalto IDPrime MD seems to fit your requirements. Some caveats:
- It tops at 2048 bits for RSA; for ECC, it supports only three standard NIST curves (P-256, P-384 and P-521), not custom curves.
- From experience, at the APDU level, the signature operation is really a command to do a modular exponentiation with the private key; thus, the hardware is compatible with all kinds of RSA (PKCS#1 v1.5, PSS...) but the hashing and padding is done on the host computer.
- The MD 830 is FIPS 140-2 lvl 3, the MD 840 is EAL 5+. There appears to be no model that is certified for both sides of the Atlantic.
- The cards are available as standard-sized plastic rectangles, nominally compatible with all standard readers; but you can also get them under the "IDBridge" format which is a USB card reader with a card in it, with a small size.
- Individual cards can be bought from cryptoshop but it is a bit unclear exactly what you get; there are IDPrime MD and IDPrime .NET cards that use the same packaging, and the latter do not support ECC (only RSA). On the bright side, individual price will be about 20€.
- The cards are supposed to be reprogrammable with custom applications (in a subset of .NET) but I never tried that and I don't know if it requires extra licenses or things like that. I think that the certifications don't extend to cards which have been reprogrammed.
As for backups, I am ready to assert that you do not want backups for signature keys. In fact, presence of a backup for a signature key can only lower the legal value of a signature (but then, this begs the question of why you would want to sign anything; a signature you generate is a legal weapon pointed back at yourself).
For encryption keys, backups are necessary to avoid data loss, and then there is no really good solution with these cards, if you want private keys to never exist outside of the certified hardware. For personal usage, even for the paranoid, you could arrange a key generation ceremony in which you generate the keys on an offline computer, booted over a CDROM and with no hard disk; the computer would then push the key in 4 or 5 smart cards, which would be so many backups.