I know I'm coming late to this discussion, but thought I'd answer for those referencing or googling the topic!
I use stew beef for souvlaki and shish kabob all the time. The 2 best ways to get it tender are:
1) Marinate over night in yogurt, just google yogurt marinades, but make sure you are using plain Balkan style yogurt
This is my favourite because it's more adaptable. Brining is not just for poultry or pork. Just google brine for beef, but this is the ratio I start with
2 3/4 cups water
1/4 cup salt
3 tablespoons brown sugar
2 cups ice
Bring water salt and sugar to a low boil to dissolve sugar and salt. Do not lower amounts of salt or sugar. These are what break down the meat fibres and make it tender. The meat will not be salty. Add 2 cups of ice and let cool completely. Place meat and brine in a baggie and keep in the fridge for a minimum of 2 hours, but preferably overnight. Rinse the meat. Pat dry. Put on skewers with whatever accoutrement you like and grill away.
That is a basic brine. I like to add extra stuff depending on my mood. During the boiling stage I'll add things like mustard, herbs, vanilla and/or liquid smoke. Many have mentioned beer. Instead of ice, add alcohol during cooling stage. I like adding Guinness. Other faves are whiskey/bourbon or a bold red wine like Shiraz. Do not add alcohol during boiling stage ( particularly whisky), as it will flare up.
Hope this helps!!
Ps- if I'm adding a BBQ sauce ( I rarely do) I only add it in last few minutes of grilling, and I try to use something similar to the brine. Guinness BBQ Sauce if I had Guinness in the brine for example.
Pps. Also makes a difference to whole kabob if you Marinate the veggies. Just use a cheap store brand Italian salad dressing. Place pre cut veggies and dressing in a baggie and Marinate for as long as you like.