If you allow for cheese, it's a piece of cake, and virtually the same as my menu for extended backpacking trips (with the only exception that I sometimes take in some of my dairy without turning it into cheese first).
Granola, dried fruit, crackers, instant potatoes, tortilla chips (I prefer blue corn) are my main carbs (with the granola,chips and some crackers adding fat, too). Beans (dehydrated refried black) and powdered hummus provide protein and carbs. Nuts and lots of 'em provide protein and fat. Cheese - string cheese for snacking and grated parmesan/romano for mixing in with potatoes ensures that the protein needs are fully met. This is all fine cookless, though the beans make a nicer soup/stew if heated at least a bit, and when cooking a little, I add some dried veggies. If willing to cook, you can of course add many other things - various carbs that need cooking, more veggies, TVP if you like it. That'll pretty much take care of your nutritional needs. You can of course add anything else that tickles your tastebuds.
Even for those who might wish to eat more than the minimum amount of complete protein, a balanced diet rich in nuts (esp tree nuts, in terms of completeness) and high nutritional value beans is going to set you up well for getting plenty without the cheese. If I were committed to going completely without dairy, I might look into how I'd cook some other complete sources like quinoa and buckwheat in the wilds, but I wouldn't consider it a necessity.
What I actually find more difficult is to find good ways to get the nutrition and flavor of fresh fruits and vegetables in the wild. Dehydrated veggies aren't really all that great, in my experience, and while dried fruit's OK, it's not the same.
P.S. Seeing that you've mentioned "calorie-dense," an addition - full-fat dairy products are usually one of the things that gets me to calorie density goals. Without that, I might add in some extra fat with coconut milk as a base for certain dishes and with some olive oil to add in to the hummus (my normal brand is low in fat).