Which algorithm can be performed by humans? Suppose I want my grandmother to perform encryption without any help from a computer, and she must encrypt the word 'HELLO' for me.

I could ask her to instead of typing the real keys, that she always hits the key thats on the right side of the real key. So that instead that she types HELLO, she types JR;;P. On my side I just look what JR;;P means, and I can decrypt that she said HELLO.

I am sure that she can do this. Is there an improvement possible to the scheme I just proposed, or is this the best the average human can do?
Every classical cipher can be used without a computer's assistance; while simple mechanical ciphers can fall into the "classical cipher" category, in general classical ciphers are pen-and-paper ciphers, almost all of which are more secure than your "press the key to the right of the real one." Vigenere, for instance, has flaws; however, it is much more secure than "press the key to the right of the real one," because the latter is a special case of a monoalphabetic substitution cipher (the whole class was broken in the 9th century CE), while the former is a polyalphabetic substitution cipher which was broken in the 19th century.

More recently, you have some newer schemes that can be done without the aid of a computer. Neal Stephenson's book Cryptonomicon featured as a plot point the Solitaire scheme, which requires only a deck of playing cards to implement. Solitaire has some weaknesses, but is likely better than Vigenere or other previous ciphers. More secure than Solitaire is RC4; this could be implemented by hand, but would be complicated (to ease matters, you could probably have a reduced-security version that could also use a deck of cards for the state).

Anything that's truly highly secure will probably be not realistic to implement by hand (except an OTP, but that's really hard to pull off the preconditions), because they are designed to be easy for a computer to do, and computers are good at different things than people. But there are certainly options better than monoalphabetic substitution.