don't rent a car in europe - it's not worth it. i got all over london and paris using their subways, and when those closed, by taxi. i bought all day passes when i was in london, and then a carnet of tickets in paris, which was a packet of 10 tickets to use on buses, short distance trains or the subway. REALLY easy to use and get around on.
if you are going to take the eurostar, i actually recommend buying them in advance. when i bought my ticket from london to paris, the price KEPT GOING UP. i was REALLY annoyed when my 110 dollar ticket jumped to 140 dollars that afternoon. the eurostar goes from london to brussels, but it doesn't go from brussels to paris, so you would need to get a eurail pass from there.
i used hostelworld to book my london hostel, which was in soho. i actually got a hotel in paris, which was the same price as a hostel. i traveled with one friend, and our hostel had doubles, so we gladly paid more to be the only two people in the room.
do you guys know french? i'd learn a couple of phrases - my friend would ask for stuff in english, and then i would ask in french. we got a lot better response once i piped up in french.
we didn't use our cell phones there - i used a phone card. i actually was the only one who ever called anyone, my friend hardly called. i missed my fiance. hehe.
i really loved the rick steves books over the lonely planet ones, because we liked his cheap travel tips. also because you are travelling during the "down" season, make sure you double check the times of the exhibits you are going to, as they have shorter hours or some things don't happen everyday (like the changing of the guard is every other day during the down season.) rick has good maps of the public transit systems in his book, but it doesn't hurt to get more - i picked up the paris maps when i bought the carnet (this was at gare du nord) and the london maps i think i could pick up a few at select underground stations.
i did the same as you - flew into london, out of paris. it was 650 after all taxes from los angeles.
if you have certain places you must visit, plan everything out in advance. we actually scheduled each day we were going to be in london and paris, from 9am to 6pm each day, to maximize our time and to know that we visited the location on the correct and open day (or perhaps the day they open late.) we also planned stuff by how close it was to other stuff.
it was a great trip... i want to go back.