Designing a Django voting system without using accounts
To address your concerns:
1: a simple Captcha would probably do the trick, if you google "django captcha", there are a bunch of plugins.  I've never used them myself, so I can't say which is the best.
2 & 3:  Using Django's sessions addresses both of these problems - with it you could save a cookie on the user's browser to indicate that the person has already voted.  This obviously allows people to vote via different browsers or by clearing their cache, so it depends on how important it is that people not be allowed to vote twice.  I would imagine that only a small percentage of people would actually think to try clearing their cache, though.  As far as I know the only other way to limit users without a sign-in process would be to test IP addresses, but that would violate your second criteria since people on the same network will show up as having the same IP address.
If you don't want multiple votes to be as simple as deleting browser cookies, you could also allow facebook or twitter login - the django-socialregistration plugin is pretty well documented and straightforward to implement.
Hope that helps!
We are considering implementing a voting system (up, down votes) without using any type of credentials--no app accounts nor OpenID or anything of that sort.
Concerns in order:

Prevent robot votes
Allow individuals under a NAT to vote without overriding/invalidating someone else's vote
Preventing (or, at the very least making very difficult for) users to vote more than once

My questions:

If you've implemented something similar, any tips?
Any concerns that perhaps I'm overlooking?
Any tools that I should perhaps look into?

If you have any questions that would help for you in forming an answer to any of these questions, please ask in the comments!