I live at sea level (literally, at sea level - it's in my backyard). Last year, for the first time ever, I didn't get headaches at altitude (5000 - 8000) hunting deer in WA and elk in ID. The only thing different - I bought the insulated 3-liter camelbak that has no shoulder straps - rather, d-rings to tie to my packframe, or just slip it in the bladder sleeve of your pack. I forget what the model name is.
Having this water accessible at all times while hiking to base camp, and hunting from there, was critical to staying hydrated. The bladder's proximity to your body keeps the water above freezing temperature - it's much easier to drink 50 degree water than 33 degree water - I get icecream headaches easily. I felt much better. It solved the most uncomfortable thing for me - the "altitude headache", which is likely caused by (or made worse by) dehydration.
The 3-liter capacity is amazing. I knew that, even if I ran it out in the afternoon, I had consumed enough water to last the day. A far cry from the one or two nalgenes thunking around in your pack.
Also, you may not want to do this in a bathtub-floor tent, but on bare ground under the tarp, the 3-liter bladder makes one hell of a pillow! Better than anything - rolled up fleece - whatever.
For exercise, you are very much on the right track with the cardio. For your legs, think about what gets tired first when you're hunting. I've always done lots of squats and olympic lifts for football, so my glutes/hams/quads are bulletproof. My calves, on the other hand, always feel worthless on the first couple of days. So, this year I need to do something which gets me on my toes, simulating long slogs up steep hills to where the bucks are. Others may have glute/ham/quad issues. Whatever. If you're not into lifting weights, that's fine.
Swallow your pride, buy a couple of used truck and tractor tires from your tire store, and tow them down the street. Take LOOOONG steps while doing so, to achieve strength over a wide range of motion. This lets you step up on that thigh-high bench or rock without looking weird. If you can achieve continuous, heavy resistance to forward movement, you will effectively simulate the hard work - walking uphill. Get creative. Tow driftwood on the beach (killer), tires on the street, tires on grass, logs on grass, scrap metal down your gravel driveway, whatever. Just get the range of motion / long stride /heavy resistance thing figured out, and make your neighbors question your sanity.
-Jerry