I've bought this game with my brother recently, and we intended to play online since I've moved out last year and we haven't been able to play via LAN since then. To my surprise, we've gotten the "Serial Keys depleted" message", and the support team hasn't replied yet.

Is there a way we could play online in the meantime, without the need to use our CD-Keys?

Yes you can. Chose IPX in the multiplayer menu (there is ipx wrapper bundled, maybe better re-download it from official author site for latest version and install as general OS solution).

You need Legacy DirectPlay enabled in OS Control Panel and IPX enabled by IPX Wrapper.

Support promise they will get last bunch of keys from Blizzard.