Any glove-like shoe will also work. There is a significant number of shoes in human history that didn't have a separate rigid sole, but were wholly made of soft leather - native American mocassins, early medieval Germanic shoes, chuvaki of people of Near Asia and Caucasus. Such footwear works quite good, unless you need to walk on paved surfaces regularly. From my personal experience I can tell that they are very comfortable in the forest.
For humans, such shoes are usually made as soft leather 'bags' for feet, but nothing prevents them from being made more glove-like for someone with longer and more mobile fingers.
As for more technological solutions, right now there exist a number of 'barefoot' shoes of sturdy synthetic fabrics with very thin vulcanized sole. Some of them, like Vibram Five Fingers even have separate fingers.
So, leather foot gloves for low-tech settings and synthetic gloves with rubber gripping surface for more advanced settings. As for the flip-flops, they can be worn over such foot-gloves when you need to protect them from abrasion - in something like medieval urban settings. In our world, medieval townsmen had worn wooden sandal-like pattens over soft leather shoes to protect them from wet, dirt and abrasion on cobblestone.
UPD: that may be a part of much bigger issue of how a race that uses the same extremities to walk and manipulate objects will structure their houses, cities and living in general. It will not be much of an issue while they are living as hunter-gatherers. As soon as they get agriculture and animal husbandry, they get problems - you do not want to eat with something you just mucked animal fecal matter with - the rate of stomach infections will be just too high. The same goes for medieval-style cities with horse-drawn carriages in the streets.
I can see feet cleaniness being a big issue, foot-bath being more important market of 'house entrance' then a door. Helping the guests to wash their feet would be even bigger marker if respect then it was in human archaic cultures.
Possibly, the structure of the cities would be different, with streets for walking being even more separate from the streets for carriages and pack animals. It would rather look like a system of sturdy poles and narrow bridges raised over the ground level.
Street food and it's consumption will also look different - from forks or other similar eating utensils being always carried on one's person, up to vendors putting the food directly into the customers' beaks.
The results for the footwear are as follows - glove-like closed shoes are better for situations where you can encounter a lot of dirt and muck. The are also better for raised walkways and poles, since the don't interfere with feet grabbing the surface you walk upon. Sandal-like footwear is more comfortable for situations where you are not that likely to encounter much dirt - for example, indoors, in big buildings where there is not much dirt, but it's impractical to wash the floor all the time.