I don't know which one is better for a 13 year old, just pick the one you know better.
My biggest recommendation, though, is that once the kid has any sort of "foundational" programming language under his belt, you write a Scheme interpreter together, in that language, and then show him that the interpreter you just wrote can run Scheme files that already exist (possibly ones you pre-prepared.) That's the best way, I've found, to burn into someone's head that there's no one-true-language, and to get their mind started experimenting with "what if the language was different in way X? Could I code that?" trains of thought.
The most important part in teaching a 13 year old programming is to let him have fun and a give him a sense of achievement. The rest will come.
And Ruby has a number of other benefits:
* Easy web frameworks if he wants to get into that (Rails, Merb, Sinatra, Camping, etc)
* Definitely fulfills the "beautiful syntax" part
* shoes for really easy GUI apps (that are portable, so he can show it off to his lame windows-using friends)
* Built-in powerful regexps for that pattern matching you expressed love for
* It's generally something that you'll run from command line, helping with the learning about Linux part
* Lots of cool libraries out there
* Object-Oriented, which at least for me was a very easy thing for me to grasp (especially compared to functional, which I'm currently trying to learn)
* Awesome