Let's start with making sure we have a clear understanding of what 'brute forcing' is.
A brute-force attack is when an adversary attempts to guess every single combination of characters, starting at one length, and increasing the length by one until the password is cracked. e.g. 1, 2, ... a, b, ... 11, 12, ... 1a, 1b, ... aa, ab, ... etc. Depending on the charset used, it can take a relatively short time to guess all possible key spaces (mixalpha), or relatively a much, much longer time to guess all possible key spaces (mixalpha-numeric-all-space). The important thing to take away here is that the adversary is simply guessing (and getting wrong) a very large number of passwords. Now..
"For the sake of this example, lets say we're talking about a linux/unix shell because this seems to be less covered."
If the adversary has local access and the harddrive is not encrypted, the password hashes can be recovered without logging in. If the harddrive is encrypted, then your main defense from password guessing attacks is configuring failed-attempt lockouts and increase the delay time after a password fails validation. From here I will be referring to an adversary that has already broken into your system, stolen your password hashes and salts from /etc/shadow, and is attempting to crack them.
"Is there a way to be certain your password can't be broken by brute force?"
No.
If the adversary is able to recover your password hashes/salts, they can begin bruteforcing the hashes on their own hardware, and you will have absolutely zero control over this.
If you are instead referring to an adversary who does not yet have access to your computer, but is trying to bruteforce your SSH login, then yes, using a firewall/IPS will prevent virtually all bruteforce attempts. Simply logging the failed logins is not enough, but using a tool that bans offending IPs (like Fail2Ban) will make attempts at guessing a quality password infeasible.
"Logging failed attempts seems like a good counter measure as well, but of course this doesn't necessarily do anything, especially if the attacker routes through a tor node and does not care if the administrator is aware they are trying to break the password."
Ok, back to remote attacks, presumably against SSH?
"...especially if the attacker routes through a tor node..."
Tor publicly lists all of their exit nodes. Ban them all.
"...and does not care if the administrator is aware they are trying to break the password."
As long as your firewall/IDS is configured properly, it doesn't matter how many different proxy servers the adversary has available to them, it would take an insurmountable amount of time and proxies to bruteforce any quality password.
"Yes, it is possible to slow down an attack in various ways, but if an attacker is perfectly okay with waiting a few years, this will not be sufficient."
Most flavors of linux hash their passwords with SHA-256. If your adversary is capable of one trillion guesses/second (as quoted by Edward Snowden a few years ago.), and you had a twelve character mixedalpha-numeric password, it would take 104 thousand years to bruteforce the little over 3 sextillion (3,279,156,381,453,603,300,000) possible password combinations. Unless you are using a password with dictionary words or common patterns of numbers and/or letters, you do not have to worry about wordlist/rules-based attacks, which in reality is the far more common and successful way of cracking passwords. This doesn't even begin to take into account the additional time spent on every connection if this was a bruteforce against a non-firewalled SSH server.
"Logical puzzles are a popular tactic, however I was considering this and it seems a human could solve and store all the answers to the puzzle database (given enough time). The data could be changed periodically but this can in turn be dealt with by a human and possibly AI scripts as well."
I don't exactly know what you mean here, but if a human can solve a puzzle, a computer can be taught to solve it in immensely less time.
