I shook hands and exchanged a few words with President Obama in 2012 at a fundraiser. Cost me $5,000, but worth it.
I shook hands with JFK as he arrived in NYC to visit his father who was hospitalized in Manhattan. This was in 1962 as I recall.
Canadian Prime Minister Kim Campbell came backstage and shook the hand of everyone in the cast of Mikado at the Stratford Festival in 1993. Considering she was only Prime Minister from June 25th, 1993 to November 4th, 1993, I think that ought to be worth some sort of prize…
I shook hands with Carter on his re-election bid in 1981.
I have had an impromtu lunch with President Obama and VP Biden. I met and shook hands with President Bush (GWB) at a trade meeting my dad was a part of and I was waiting in a hallway in the Old Executive building and had President Clinton and a herd of reports and SS guys come by and pile into the elevator across from me.
I also sat next to President Carter on a plane, but that was in 2008, well after he stopped be President. Had a great talk with him about his humaniatrian activites though.
Well, the closest I can come doesn’t involve me but my brother. He was working at a grocery store in high school when Dan Quayle’s motorcade stopped so the VP could get some cookies and lemonade.
Shook hands with both Bill and Hillary on the POTUS visit to Uganda. Attended a rally for Obama in 2012, but got no closer than about 30 feet.
Technically the prime minister is the head of government, not head of state ;).
I was within 10 metres or so of Adrienne Clarkson when I was eating at a restaurant in Ottawa and she walked past with an insanely small (visible) security detail.
I’ve been standing on the footpath when the Queen’s car drove past. So 5 metres or so I suppose.
I’ve met the Governor of NSW, who is the vice-regal representative.
One guy I worked with years ago in a non-political job went on to become the president of an eastern hemisphere country that is unfriendly towards the US. I was his boss for a while. It has been many years but I’m sure he’d remember me, and sometimes I wonder if we’d ever sit down and shoot the breeze over a coffee or beer. Not likely, but it would be cool. If he came by my area I’d try to contact him. I bet that would draw interest from the CIA.
And, a high school classmate of mine went on to become US Ambassador to one of the top countries in the world. We were on the track team together. He’s now a personal friend of Obama, and it’d be very cool to get to meet him.
I doubt any of those things’d happen though. I’ll just be happy living my simple life.
Especially with a user name of “Bullitt.” 
My wife has met and chatted with Queen Elizabeth, but I’ve only managed to be about 50 feet away on a couple of occasions.
We move in semi-exalted circles.
I shook hands with Barack Obama when he was running against Bobby Rush in Chicago I also drove past his house before he was President.
It’s extremely doubtful that either event had the same significance for him.
I think I may have found a tiny flaw in his strategy.
If you could write a mystery short story with highlights of that information, and maybe throw in a recipe or two, that would sell. No heads of state need appear directly.
Dubya came to give a speech in our Civic Auditorium back when I worked at City Hall (kitty-corner across the street from it). I can’t remember whether I saw the limo drive up or not. But we were all taking our breaks at the windows, watching things being set up and people standing in line.
Yeah. We were on the third floor and got a good view of the sniper’s nest on top of the auditorium.
On two occasions (about 30 years apart) I’ve been within a couple of metres of Queen Elizabeth II as she slowly drove past.
When Obama is in San Francisco he stays a block away from my office. They close the street even to pedestrians, so it’s not particularly fun. And no, I’ve never seen him.
I saw QEII (the person not the ship) in a motorcade when she and Philip were visiting San Francisco, a number of years ago. Yes, I actually saw her face and her waving hand. So maybe 10-15 feet away.
And I was within spitting distance of Ahnold once while he was the head of our state. 
(He’s shorter in person).
I was spanked by Grover Cleveland on two non-consecutive occasions. Aside from that, he closest I’ve been is in a smallish auditorium with candidate Obama (not president yet).
George HW Bush was the commencement speaker at my college graduation in 1992 while he was still in office. Most everyone I knew had talked about booing, but ultimately we decided to do absolutely nothing to endanger graduating and getting the hell out of there.
This doesn’t count for the purposes of this thread, but in approximately that same year, I shook hands with Robert F. Kennedy.
He appeared on a local television discussion show. My uncle worked at the TV station, and he arranged for me and the station manager’s son to shake RFK’s hand when he walked out of the studio and into the lobby.
I was around 10 years old at the time.