I did something similar albeit not so cool and without the intent of dating but with a backpack. Hiked and Hitchhiked a few weeks through Europe with a girl. We met through a "looking for hitchhiking partner" forum. It was tremendous fun. We almost had no money and no iSomething but met a lot of nice people and got around very quickly. We also showered and changed clothes every few days. Smelling like shit complicates things. Hitchhiking is far easier if you look and smell "normal".

I remember driving a BMW from the 7 series into the sunset heading to the atlantic ocean in france. I have the credit card of the car owner next to me (for the toll stations) as he is sleeping and we are listening to his favorite french chansons. He was a banker not much older than me. This connected feeling and trust is priceless and I'm really flabbergasted every time it works. There is a longing in the people you meet on your way and a longing in yourself. Nothing beats someone who stops and offers you ride after you were stuck for 6 hours in a godless place surrounded by refuges who are trying to enter great Britain in the back of trucks that cross the border. And you suddenly realize how important that passport in your pocket is. And how lucky and privileged you are and what desperation does to people. I don't know. It changed my perspective on a lot of things.

If you are careful with your money and avoid tourist areas and research cheap spots before going to big cities (more expensive if you don't know where to live on the cheap) you can travel for 4 weeks for 500 to 1000€ in western europe using only a tent and a small backpack. In eastern europe it is probably cheaper. We also went to restaurants quite often - so we were quite wasteful.

But if I would do it next year again I'd also take a smartphone with me. There is the great hitchwiki.org and Couchsurfing and other internet services would help me save money and time. This was in 2007.