Well, it's up to you, but the best way I know of spreading the Gospel is to demonstrate the Gospel as much as possible in our actions. Let people know that you care for them and love them, even though they probably are strangers.
It can be argued that you handing them icons and prayers is an expression of this love, and those arguing such would be correct. However, my experience has been that a kind word given in a loving tone of voice and demonstrating concern without prying into anyone's business shows that you are concerned about this other person. People respond to this, since they are perceiving that you are part of what they are searching for and are what we were made to be: to live out our lives participating in the Divine Life here on earth.
Don't take me wrong; your idea may work because that may be what you have been called to do. However, I know what works through me, and I have long said that we will never argue anyone into our churches, we can only love them into our churches.
May theh Lord bless your efforts, whichever path you take.
PS. Send pictures of your travels!