If you give up on February and just resign yourself to treating it as an exception, then the formula in the article, 30 + (x + [x/8])%2, is trivial to compute in your head.
Zeller's Congruence is quite a bit harder to do in your head.
For mental calculation of day of week, I use a method given in a Martin Gardner book, but this only works for 1900-1999. I'll give a fix to extend it to other centuries.
Let Y be the last two digits of the year, let M be the month (1-12), and D be the day of the month (1-31). Let [X] denote the integer part of X.
Compute w = [Y/12] + Y%12 + [Y%12/4]
Compute w = w + month_offset(M), where month_offset is defined by this table:
M month_offset
1 1
2 4
3 4
4 0
5 2
6 5
7 0
8 3
9 6
10 1
11 4
12 6
Compute w = w + D
w%7 gives the day of the week, with Saturday being day 0. A couple notes.
1. You can reduce mod 7 as you go. For example, to get the day of the week of 1969-07-16, you could think "[69/12] = 5, add 9 (69%12) giving 14 == 0 mod 7. [9/4] = 2, so we are at 2. Add month_offset(7) == 0, giving 0. Add 16 (D), and we have 3 mod 7, so Wednesday".
2. Month_offset is easy to remember if you think of it this way:
1 4 4
0 2 5
0 3 6
1 4 6
That's 12^2, 5^2, 6^2, and 12^2+2. I don't know why that makes it easy, but Gardner suggested it, and I have not forgotten it in something like 40 years, even though I rarely use it.
3. If the year is a leap year, subtract 1 for dates in January and February.
4. For years in 2000-2099, subtract 1 from the result. For years in 1800-1899, add 2. If you forget what the century correction is, you can work it out in your head. For instance, to find the correction for 20xx, work out the day of week of 1999-12-31: 99=12x8+3, [3/4]=0, month_offset(12)=6, so 8+3+0+6+31==6 mod 7, or Friday. Now work out 2000-01-01 without a century correction: 0=0x12+0, [0/4]=0, month_offset(1)=1. 2000 is a leap year, so need to subtract 1 in January, so we have 0+0+0+0+1-1+1==1 mod 7, so Sunday. However, it should be Saturday since it comes after Friday, and so the century correction must be -1 for 20xx.
5. Gardner's method is really one of the other well known methods (I forget which one) adjusted to make mental calculation easier.
Addendum: this is described in chapter 7, "Tricks of Lightning Calculators" from the Martin Gardner collection "Mathematical Carnival".