I'd try making multiple accounts less attractive alternative than having a single account. Maybe have users accumulate privilege like SO through good behavior (new accounts have little privilege but can do very little) so the effect of the ban is losing all privileges? Possibly only do silent bans, so banned users aren't aware they've been banned, but their activity isn't seen by anyone else?
If you have to ban a user and want to identify them somehow, I'd rely primarily on IP address recognizing that (a) savvy users will have multiple IP addresses and (b) could be sharing IP addresses with non-banned users.
I would not user browser fingerprinting like panoptclick.com (trivial to change the fingerprint - e.g., use a different browser (firefox/chrome/opera/konquerer/safari/IE) or computer, change your user agent string; install/uninstall fonts/plugins).
I would not use evercookie -- easily avoided by changing computers or virtual machines and somewhat unethical.
You also may want to build in a remedy for users who claim their IP address has been banned who have never misused your service. For example, today 100.101.102.103 is assigned to user A who got banned by your ISP, tomorrow it is assigned to user B who is good and should not be banned (especially common for mobile devices). Or you share a wifi router with several people in an apartment who want separate accounts, but all appear to have the same IP address on your account (e.g., your router uses NAT).
Remember, websites operate on TCP. So it is not trivial to spoof an IP address; your IP address is like a mailing address -- it contains routing information and TCP requires a back-and-forth handshake before sending information like a web page GET/POST request. So while its easy to lie in during the initial step of a TCP handshake and say I'm at fake IP address that resides California rather than your real IP address in New York, the packets will be end up being routed to some computer in California rather than yours in New York and since you'll never see the servers responses you won't get to complete the handshake and make the request (unless you control the computer in California (or an intermediate router) and forward the packets back to your computer or end up guessing the correct 32-bit integer (1 in 4 billion chance) from the server).
Granted it costs under ~$5 to legitimately get another IP address to set up a proxy and most tech-savvy people already have several IP address they could use. But it becomes less convenient for them to do so.