Are there public slow-but-strong algorithms out there that resist brute-force attacks better? I'm reading that AES uses 4x4 bytes (4*4*8 = 256 bits key) matrix for performances matters (since it's a requirement for common standard encryption algorithms), but are there implementations with choosable key size for this particular algorithm, so I can make brute-force attacks harder with a good password ?

Also, if I'm worried that I can't make user use good passwords (it's a shame, but lets imagine that), can I make an algorithm deliberately slow to make brute-force attacks infeasible with weak passwords, but really secure ?

Could we one day make users switch to key files instead of passwords to completely forget about brute-force, even with the potentially theft of those keys ?
Bruteforcing the AES algorithm itself (i.e. trying all possible keys to encrypt or decrypt some blocks to see if they give the right result in a known-plaintext attack or similar) is not really a problem, even in the 128-bit key version.

(This takes on average 2127 tries. If you can try 230=109 AES-keys per second, it will still take around 5·1021 years, much longer than the universe existed, and any life will exist. Parallelizing this makes it faster, but there is some limit, too ... if you can calculate on 109 processors in parallel, it still needs 5·1013 years ... about three times the estimated age of the universe until now.)

So, the attackable point is not bruteforcing the AES key, but bruteforcing the derivation of a key from a password. And here is where we have to enforce our design. You should not use the password directly (maybe with padding) as an AES key. Instead, use a slow password derivation function, and incorporate some salt.

NIST proposes the PBKDF2 construction based on iterated calling of some fast hash function. Setting the iteration number high enough will make it slow enough. 
PBKDF2 is easily parallelizable on GPUs, which makes brute-forcing slightly faster than we would wish, though.

Other alternatives might be bcrypt, or the newer scrypt.
These are firstly slow hash functions for secure password storage, but I think one can also reuse their output as a key for AES or any other symmetric cipher of the right key size. (You just have to think of a protocol to transfer the salt.)