Muscle gain and fat loss CAN happen at the same time. 1lb of added muscle burns around another 45-50 calories, as muscle is metabolically positive.
It should be noted this would happen for a time, but diminsh at a later date, when an increased caloric intake could evnetually create increased levels of fat storage, greater than any added muscle could help to burn, causing net fat gains not net losses.
Protein shakes can be left on hold for now, as you need to really get your training and diet in order first of all.
In terms of training the basic full body system, is usually best for people adjusting to the biomechanics of weightlifting.
You perform 2 sets of 8-10 reps per muscle group, utilising all muscle groups. Mostly compound movements that work multiple muscles, like Squats, Deadlifts, Chin ups etc etc, but you could potentially add a bit of direct stuff in as it's known like Curls, Pressdowns, Planks etc.
3 times a week is all you need.
Cardio wise, steady state or interval at a low setting for starters, just to get a slightly better foundation for your cardiovascular system, that can then be built on, then when ou sep up hte intensity of your weights after around 4-6 weeks of adjustment, the same for Cardio can happen to, to keep both in synch.
I'd favour interval at that point as it's less adaptive than steady state, because you might use the same setting time after time, for a number of weeks, but the fluctuation in intensity with every session, is not as repetitve as steady state is.
This is an example of how you could work the system initially.
Day 1. Weights
Day 2. Cardio
Day 3. Weights
Day 4. Day off
Day 5. Cardio
Day 6. Weights
Day 7. Day off.
This stops you training for more than 3 days straight and stops you doing nothing for 2 days straight, by splitting the off days.
Don't cut calories on a cut shift them. You could cut some carbs on a cut, which would cause an energy surplus, that Fat would fulfill and you could replace the reduced calories the Carbs were providing with Fat calories, so you'd be maintaining the same calories approximately, but having a different Macronutrient ratio.
Cutting calories would just probably to some extent negatively affect muscle mass and unless you were preparign for a bodybuilding competition, getting off a Steroid cycle, or got injured, then muscle mass loss shouldn't need to happen.
You can bulk first if you wish, but be cut friendly. By this I mean don't overdo the calories and put too much fat on as well, making it more difficult, arduous and longer to cut.
If you're eating 6 times a day, go for an average of around 400 calories a meal for now, with around 1.2g Protein per lb of bodyweight, which for you would be around 210g a day, or roughly 35g per meal.
When you stop gaining at some point, add another 50 calories per meal, so you're getting a 300 a day increase. This in you case could be around 50 / 50 Carbs / Fat increase per meal.
Do this every time you stall, otherwise if you just jumped up by 1,000+ calories a day, you'd get too much excess converting to Fat, that would dissipate or diminish over time, the more calories were needed to grow, but then you'd almsot certainly have more fat to try and cut after a bulk, as opposed to gradual caloric increases as and when required.
I'd be very suprised if your body stalled on the bulk and 300 more calories a day, did nothing to help.
Running cna burn muscle, but only after calories in the main. You would burn muscle training on empty, but if you give the body something, even a dextrose drink, or a banana, or a Ham Sandwich, your body should burn the fuel first, then resort to natural resources like muscle, so doing some cardio for about 30 minutes a time, won't serious hinder a bulking phase.
Hopefully all that makes sense.
Oh and forget an Abs machine they're pretty mongy. You can get Abs work by doing compound exercises that target the lower back and Core, plus other things like Planks, Roman Chairs, Leg Raises, V-Crunches etc.