Sounds like a tall order. Before you begin, understand that you are bound for a world of pain as your body reacts to a sudden increase in activity with DOMS (Delayed Onset Muscle Soreness). If you are pretty much detrained, then you have a short window of time where you can make increases every day.
Starting Strength, now in it's 3rd edition, is a very good beginner program. For the first week you can probably do the full body workouts every day. As soon as you stall for the first time, go back to the normal training schedule of 3x per week. Your body needs rest to rebuild muscle.
It's best to have conditioning after you do your strength training. You don't want to fail a squat and be pinned by the bar because you just exhausted yourself. All you need is about 20 minutes of good conditioning. HIIT, running intervals, tire flipping, sledgehammer work, hill sprints, etc. The idea is to get your heart rate up to the top end of the anaerobic zone, and then let it rest down to the top of the aerobic zone. Try to get more and more work done as your heart rate increases, but start slowly and build up.
Both Yoga and Pilates are very good at helping your flexibility, as well as supplementing your core strength. The extra benefit they provide is that it will help your muscles release the buildup that causes more severe DOMS.
Alternatively, use foam rolling and a good stretching routine. You don't really need the strength aspects of Yoga or Pilates, but the stretching will help.
You want to get the nutrition dialed in, but be smart about it. There is nothing wrong with intermittent fasting, as long as you get your dietary needs taken care of. Understand the following about the macro-nutrients:
- Your body needs protein to rebuild muscle. Since you are trying to get strength training in, you need more protein than is required for simple maintenance. Protein has an added benefit that it burns more Calories just to process it. Try to get 1g protein/pound total body weight every day (or equivalent averaged over a week if you incorporate fasting days).
- Your muscles need energy. Carbs post workout are the quickest and easiest way to replenish lost energy and aid recovery. However, your body can get energy equally from fat.
- Fat fills in the rest.
Perhaps a more sane approach
I've been reading up on Jim Wendler's 5/3/1 program, and there is a lot to like about it. With a couple adjustments for a beginner, it can be a killer (meaning good) program for you. NOTE: if you want to buy the eBook, use the lower set of "Add to Cart" buttons.
Wendler's philosophy is that every truly successful training program needs the following elements: strength training, conditioning, and mobility work. There are several different variations he covers in his eBook to help with scheduling. One of them is 2 days a week strength training with 3 days of conditioning/skill work/mobility work. The normal approach is 4 days/week strength training, and then you tack the other stuff on to the training day.
The only modification that a beginner would need to make is to make your increases every session. Increase your squat and deadlift by 10 lbs and your press and bench by 5 lbs every time you do them. The first time you stall on a lift, slow down and do it the way Wendler outlines.
The biggest thing to watch out for is being able to recover from your last training session to be ready for the next. Starting Strength is a very good beginner program, but it is designed around having a full day of rest in between because you are doing a full body workout each time. Wendler's 5/3/1 is a more advanced program, but you are focusing on one lift plus assistance for that lift each session. You have a day devoted to bench, which you can follow by a day devoted to squat. Etc. This allows your upper body to recuperate while you train your lower body, and vice-versa.
Another important aspect is to eat. Eat enough to recover, but not so much you gain weight. I guarantee you even if you increase your food on training days by 20% and cut your food by 20% on rest days you will still have a net deficit after you factor in all the work you are doing. In fact, that's the intermittent fasting protocol for "recomposition" (gaining strength while losing fat). To be fully compliant, all you would need to do is limit the window of time where you are eating to 8 hours or less.