If you are worried about a "leaked database" scenario (rather than the online cracking vector, which can be mitigated by per-user, per-IP, per-site rate-limiting and lockout) then you are right that hashing is not enough.
Even using the most complex sequence of hashes & salting e.g. bcrypt(pbkdf2(sha256(pin),salt1),salt2) you are still going to be vulnerable to anyone who can see (e.g. from a source code/docs leak) what algorithms are used and who can find your salts (normally stored in the same DB/table) -- they can just run the same series of hashes, and even if it takes a minute for each that's only 7 days to try them all. So you would basically be relying on security-by-obscurity.
In this case it would be worth encrypting the password hashes with a secret key (which can be kept separately from the source code, only accessible to trusted "production security operations" users, never re-used in pre-prod environments, changed regularly, etc.). That secret key will need to be present on the server which validates/updates PIN codes, but it can be kept separately from the user/pin database (e.g. in an encrypted config file), which means that Little Bobby Tables won't automatically get access to it when he snarfs the whole of T_USERS via SQL injection, or when someone grabs a DVD with a DB backup on it from your sysadmin's desk.
[Normally encrypting the hashes is not recommended, because its better to use a secure hash, good salt and strong password/phrases, and encrypting the hashes can give a false sense of security. But if you can't have strong passwords then there aren't many other options -- beggars can't be choosers...]
You could combine the PIN with a password -- but in that case why bother with the PIN at all? Just require a strong alphanumeric password. (If the PIN is used in combination with a smartcard or token or similar, of course, then it can add to the overall security.)
We could use a bigger (6/8 digit) PIN. Its not feasible to make a digit-only PIN be secure from brute force: at 1B hashes per second, we'd need 16 or more digits to push the brute force time beyond a year. But adding a few more digits might be enough to make the online attack easier to detect and block -- with only 10K combinations its going to be hard to set "slow-force" thresholds low enough to make an attack infeasible. Unfortunately, you have likely have physical constraints (hardware selection) which preclude longer PINs.