Depends on where in the middle ages.
The Greek diet used grains, but was also heavy in legumes, vegetables such as artichokes, peas, and olives, and meats such as goat, fish, and fowls.
Rice was available in Byzantium and Spain.
The Spanish used so many nuts and garbanzo beans in their diet that during the age of sail, scurvy was known among Spanish sailors as "The Dutch Disease" as the Spanish sailors rarely got it. Of course, they had no idea why.
Avoiding grains and milk in the south may be a bit expensive, but should be possible. The hardest part may be getting enough protein, as it was for everyone at the time.
Pick a country where you want this story and do a deep dive into their available food. It will add to your character's adventure.