Alternatives to php for in-line web programming?
You've hit on the big reason why PHP is so popular - it has all of those pieces in a server-embeddable package. There aren't really many solutions with its ease of deployment; PHP is written specifically for what you want, which is both its strength and weakness. It's why it's such a weak general-purpose language, and why everyone and their dog knows it. It's everywhere, and the barrier to entry is near zero.
PHP is a language plus templating plus a web framework all baked into one package. To get an equivalent, you're going to need a web framework, even if it's a small one. Something like Sinatra is a super lightweight way to do similar in Ruby, though it requires a separate server process.
You could look at something like Perl with cgi.pm, but it may be a step in the wrong direction if you're wanting something cleaner than PHP.
I don't know Python packages well enough to offer suggestions there, but Twisted makes it easy to bind a Python program to a web interface. That does end up running in its own server process, though.
You'll need to do a little more work than your standard PHP deploy if you want to use something besides PHP, but that's often a choice that people consider to be a reasonable tradeoff for gains in productivity.
Python Flask is a good web framework: it fits your requirements, easy to learn, and scales gracefully. Go through the tutorial to see!
I have three suggestions.
The first is Ruby on Rails - It's pretty fun once you get into it.. I would recommend going through Rails for Zombies to get a general idea of whether you like it or not.
It's really easy to get something up and running on Heroku for free, so you don't have to spend any money to get something up on the web..
My second suggestion is one I'm just trying out called Node.js. I'd recommend watching this video to get an idea of what it's about:
http://www.youtube.com/watch?v=jo_B4LTHi3I
If you're into Javascript, I think you'll get it right away. You can also build an open source Node.js project on www.cloud9ide.com which is pretty nifty too.
A third one, if you're into learning Java, is "Play". A cool video on this is:
I haven't used this much, but it's on my "to do" list of things to check out. Overall, I suggest just dipping your toes in the water for a bunch of different frameworks and get an idea of how they work and then you'll naturally pursue whatever makes the most sense to you. Good luck!