I would go with Python + Postgres
Python because there is less stuff all bundled into the name space when compared to PHP which has a bloated name space.
Postgres because it works more like Oracle and other higher production databases.
MySql misses things that work everywhere and implements tricks that aren't used anywhere. Auto_Increment is an example of the latter.... not having the ability to set functions as a default value is an example of the former.
I will echo Tangor's sentiment that it is best to learn to program. The language doesn't matter, it is just a matter of sytax at that point, so I would say teach them to program, then give them a language.
I still like Python for starting out as the name space is light. For example, I feel like it is a better path to learn to code in a method that sanitizes string inputs for DB inserts/updates than to teach them to wrap it in mysql_real_escape because that doesn't teach them how mysql_real_escape works.