Are we allowed to lie in our profiles?
Yes. There is no rule that requires honesty. There are people say they are located in a fictional place, for instance. And our beloved Shog9, who is always looking over our shoulders (in the nicest way possible, and of course, we're all happy to have him there), says in his profile that he's "Not looking over your shoulder".
The accepted answer on the Meta post about profile content reads as follows:
Generally speaking, your profile is (to an extent) fair game, as it is a reflection of you as a person, not the site as a whole.
Self-promotion, your e-mail address, humor, (if you know HTML) imagery and even the f-bomb are allowed there.
There are reasonable limitations for all of those, but generally speaking, unless you're a hard-core spammer or you put something truly offensive / crazy in there (like hate speech or pornography), you'll be OK.
Also, understand that all links are no-followed, so SO doesn't actually give you Google Juice from your profile.
And Jeff Atwood said, in another Meta post:
The user page is a reflection of that user and it is their page to do with what they will.
(Within reason, of course.)
We also allow explicit self-promotion on the user page, which is not allowed in posts, either.
Is Rand lying?
No.
From the reputation history of Rand's account:

I'm not willing to go through his profile's "reputation" tab and add up the gains for each day over the past 13 months, but if you were inclined to do so, you would certainly see that the sum total is in the ballpark of 26,500. Rand is imperfect, like all of us, and he has his faults, as all of us do, but I am confident in saying that dishonesty is NOT among those faults.
On the merits of the way this question and the way it was written:
On a side note, if I were you, I'd retract my assertion that Rand's rep count is "obviously not possible", and its implication that he is lying. Not only is his rep count possible, it is a fact.
As I see it, this portion of your question is a clear violation of the cardinal rule of Stack Exchange: Be Nice
Rudeness and belittling language are not okay. Your tone should match the way you'd talk in person with someone you respect and whom you want to respect you. If you don't have time to say something politely, just leave it for someone who does.
Don't be a jerk. These are just a few examples. If you see them, flag them:
Name-calling. Focus on the post, not the person. That includes terms that feel personal even when they're applied to posts (like "lazy", "ignorant", or "whiny").
It would have been easy for you to ask about dishonesty in profiles without putting another user on the hot seat and implying that said user is dishonest. That hypothetical version of your question would have been valid, and I wouldn't have taken issue with it. But when you call a specific user's personality and integrity into question, you cease to "Be Nice", and the validity of your query gets lost amid the accusations and ad hominem attacks.