Italy - Stuck on a specific destination!

First time in Italy? Fly from London to Venice. Spend 2 nights in Venice. Take a train south to Florence (2hrs) Spend 2 nights in Florence Take train south to Rome (90 min). Spend 3 nights in Rome. Fly out of Rome. You've done Italy's 3 bigs in a week. You've got your feet wet.
Next time you can explore more and better.

Italian Youth Hostel Association http://aighostels.it/ More hostels on the web
http://www.ostellidellagioventu.org/ However a single person might be able to find a budget hotel for 75 euro (C$100). Give it a try. Use any search engine (booking.com, venere.com, etc). Italian cuisine has plenty of vegetarian option. When I was living in Florence, in the 1980's, I used to go often to this vegetarian restaurant, the first and most famous in town. They are still around and they are as popular as ever: http://www.il-vegetariano.it/ My friends told me there are many more now. Haven't gone back to that one during my frequent visits, but it was good, I recommend it and I read it's still Florence's no. 1 choice.

Another possibility for budget accomidations are convents and monasteries. You should be able to get a room with breakfast for 50 to 60 Euro in the major cities, less in more remote areas. MonasteryStays.com will do the booking for you (with a small fee included), or you can book yourself via email and Google Translate. You would need to live by their curfew, and don't expect English to be spoken, and no TV/radio/concierge/etc. PM me if you want recommendations for Florence, Rome, and Venice. And FYI, Italy is an easy place to travel as a vegetarian. Lots of options for meat-free pastas, salads, pizza, and soups. If you're concerned about details of broths used, learn a few key questions, or write them out on cards.

Check out Orvieto as an option for 3-4 days before Rome. Great food, day trip to Civita di Bagnoregio, good transportation connections, 1.5 hour train trip to Rome, very scenic, interesting museums...just one possibility of many!

I think that being a vegetarian in Italy is pretty easy! Bread, pasta, and vegetables cooked a million ways should make you a happy backpacker! Have you considered spending time in Siena? It's a great town, with a great vibe, a young population, and great night life. You can take the public bus to some of the surrounding hill towns or take organized tours out to them in a group. Great history, wine, sunflower fields in summer, and food! Haven't stayed in the hostel in Siena but have stayed in others in Italy and had great experiences. We once stayed in Siena at a convent called the Hotel Almadomus run by the nuns of St. Catherine - the saint's head is still in the church next door, kept as a relic. Anyway, most of the rooms have SWEEPING views overlooking the city (you have to request this or you might be facing a wall) and the price is great. Simple accommodations but a unique experience and perfect for seeing Siena and the surrounding area. http://www.hotelalmadomus.it/inglese/paginaprincipale.php#.Ua1UH0DVCDs
Good luck with your plans and have a great trip!

I like Roberto's itinerary. In Florence, Archi Rossi Hostel is great. They have a few single rooms, but you have to book well in advance.

I also agree with Venice and Florence, having just visited both last month. I was surprised by how many restaurants offered vegetarian options, so I think you'll be fine.

Mike, I'm planning my own trip to Italy, so I cannot yet comment on your question there, but Cinque Terre or Siena come to mind. I have been to the Goodwood Festival twice. You will love it! If you get a chance, the Millstream Inn is a lovely place nearby to spend the night or have dinner. Also, if you get the chance to get down to the dockyard in Portsmouth, the tour of the HMS Victory is wonderful and well worth the visit. Finally, for the best scones in all of England, Belinda's in Arundel. Happy travels :)