Or would it be better for me to just practice on my own PC (winxp)?
There are a number of projects and products out there to help you setup and manage a LAMP server. (I happen to work on one, that is available in a free version: http://www.virtualmin.com )
A week or two of that and you'll have a good idea of what you want and need out of a host. The free options aren't going to give you a lot of flexibility...App Engine gives you a Python and Django environment, but the back end is downright bizarre if you're following along with traditional MySQL and LAMP based tutorials. Heroku is awesome, but you get what they give you (Ruby On Rails). If you need to send mail, you'll have to ship it out through someone else (possibly GMail), as you won't be able to run local SMTP.
But, if you're just tinkering, you can probably get by with anything that allows you to run the kind of apps you want to build.
Heroku - Rails
localhost with dyndns
virtual machines