Animals are always less efficient then plants for providing food. Think about it, you still need plants of some form (plankton counts as 'plants' since they use photosynthesis) to produce the energy, and then something to eat it. All the energy the animal spends eating, breathing, growing, mating, and having young is energy that is 'wasted', The animal is going to need substantially more energy in it's lifetime then you get out of eating it, and thus is going to eat substantially more plants.
There are two reasons we grow livestock despite this (well three if you include 'i just love the taste of sausage over corn').
Humans need a certain amount of proteins and other resources that, until very recently, could only reliably come from animals. We know know enough about nutrition to allow pure vegetarians to exist and be healthy, but they do have to be very careful about what they eat to ensure they replace those resources that our body evolved to get from animals.
Some animals can consume resources we can not able to consume ourselves, thus converting a source of energy that we could not utilize into one we can. Sure the animal may waste 80% of the energy consumed, but that still gives us 20% of the consumed energy rather then the 0 percent we would have gotten if we just left that inedible grass untouched.
Option 1 doesn't really apply if your looking to use animals as your staple food (except in reverse, you need to still make sure you get enough plant to avoid scurvy and other nutritional issues).
Thus option 2 is the important factor in making livestock a productive option. To make your animals useful they must consume something that humans just can't consume otherwise. If not they are an extravagant waste.
Keep in mind that most places where grass can grow plants can grow, so making a situation where there is plentiful food to feed animals but where you can not eat the food yourself, and you can not plant foods you could eat, takes some work. Generally this is going to be limited to areas where even grass has difficulty growing, and thus any other plants will struggle and die before bearing fruit. This would, however, limit your food supplies.
In your world there is plenty of life around you, and if not they can move to a place where there is more life easily. The best option for exploiting the existing life would be to catch animals and gather food directly, use of livestock that consumes anything humans can eat will be too wasteful.
If you wanted to make livestock viable the biggest thing you must consider is not how fast the grow or health, but what they eat. All livestock must consume resources that humans can not, none of it can be eating things humans can eat or it's a waste.
This makes grazing animals possible, however, not everywhere the humans travel will have large grazing lands to consume. That makes feeding the livestock while traveling through areas that don't have heavy grasses difficult; where there aren't grasses you have to feed your livestock from your own food reserves and thus they are a liability.
In this situation the best solution would be have lots of livestock while in areas with lots of grassland, and very little in areas without it. In other words your want to butcher and eat most of your livestock when leaving grassland areas, keeping only enough breeding stock to start up a good herd later.
This suggests your want livestock that is smaller then the traditional cows or even pigs we use. Your want comparatively small creatures that have short life cycles. Thus it costs you less resources to keep a breeding stock alive when there isn't grassland (they don't eat too much), and their quicker breeding cycle means they can quickly (and exponentially) to fill up large grasslands when you find them.
You would likely be breeding your own grazing creatures. They would grow to be potentially quite fat for their size (mostly meat not bone, like modern cows), but smaller (not as tall or big as a cow, despite having the same proportions as one). The creature would likely be one that is very good at adapting to available food as well. When it's starved it stays somewhat skinny, when it has lots of food it eats up and throws on lots of fat reserves, doubling or tripping in size. This allows them to not be too expensive to keep while traveling, and still be useful for harvesting when you have grazing lands.
I describe what the creature is like because humans will make it! You can do some amazing things with breeding, compare a Chihuahua to a wolf, or maize to modern corn. In a short period of time we have bred creatures to be substantially different from what they started, and to better meet our needs. Modern animals that are slaughtered for food could not survive in the wild, we have bred them to be so full of fat (that we can eat) that they are slow and unable to fend for themselves. We've even bred dogs that can not even reproduce without human intervention to meet our needs. Humans will decide what they want their livestock to look like, and breed those traits into whatever animal they started with.
As I said in your first question I imagine flying creatures would be some of the most common non-aquatic species, due to the ease of migration. Thus another common creature would be some sort of 'flying' livestock. This could come in two forms. The first is one that survives off of bugs (like bats), but is bread to put on more weight and produce lots of milk/nectar. They consume all the tiny bugs that are too small to be worth catching and eating for humans, but produce something humans can use. They wouldn't be your primary foodstuff, but it is a 'free' supplemental source of food, for a group that can't rely on growing their own finding ways to exploit all available food in an area will be important.
They will likely use hawks to hunt flying animals as well, though this will likely be more about training them to catch food and bring it back to humans then letting them hunt their own food to fatten them up.
