Quasar. Your routine isn’t unhealthy, but don’t be surprised if it doesn’t help you reach your goals.
“Would adding more cycling... and running/sprinting to the routine help?” - Probably not, and the main problem here is the word “more”. Cycling, running, and sprinting are good cardio exercises, but it sounds like you’re already doing too much (or deviating from your goals at the very least). Burning 800-1000 calories a day in a single exercise is overkill. If your goal was to build up to doing a marathon, that would be different, but your goal seems to be getting in shape instead. Burning something like 500 calories for a cardio session is plenty to reap the benefits from it, and another consideration would be to incorporate 15-30 minute HIIT sessions in where you give maximum effort in a relatively short period of time. Jogging and cycling is still fine, but having a more diverse training routine will lead to a more balanced body.
“Second, I have never done strength training my whole life. Could you suggest extremely basic exercises to start off with?” - I feel like this question is misguided. While there are certainly exercises that involve intermediate-advanced level movement patterns, most things you encounter will have relatively simple movement patterns. Even advanced lifters are using basic exercises to build muscle and stay in shape. Your strength training experience shouldn’t effect what kinds of exercises you perform. Instead, your current physical strength (at any given time) should indicate an appropriate level of resistance for your muscles (in general how much you lift). Doing any exercise in proper form is very important too, if you can only go up to 5lbs while maintaining proper form, then that’s all you should do - 5lbs in good form is better than 10lbs in bad form. Never ego lift.
"How do I improve core strength?" - Like any other muscle group, resistance training will improve strength, endurance, and size. Some exercises are more useful than others, and this video looks at which ab exercises are known to best activate the abdominal region. The linked exercises are the weighted crunch, ab roll out, vertical leg crunch, stability ball crunch, knee raise, and bicycle crunch. While these alone can give you a decent amount of variety, I wouldn't consider them as the only ab exercises you should be doing. This video looks at the various functions of the abdominal area along with suggestions on how to train them.
What then would I suggest? First is understanding this; Your activities will determine your shape, while your nutrition will determine your size. So if your activities are that of a couch potato, then your shape will adapt to that of a couch potato, and your nutrition will determine if you are a big or small couch potato. Likewise, if you activities are that of an athlete, then your shape will adapt to that of an athlete, and your nutrition will determine if you are a big or small athlete.
Once you understand that, I would suggest finding a fitness program that was put together by someone who knows what they are doing. StrongLifts 5x5 program is a VERY simple free option, and AthleanX has several programs available for purchase depending on your goals and fitness level/experience (they also have a plethora of free informative videos on YouTube). Following a competent program will make a world of difference compared to making things up based on a limited understanding.
On the nutrition side of things, you’ll want to pay attention to your “TDEE” (Total Daily Energy Expenditure) which is how many calories your body consumes each day (to maintain itself) given all your activities. If you are looking to lose weight, subtract 10-20% off the top of your TDEE and eat that amount daily. Protein is very important, and you’ll want to aim for eating 1.5-2x your kg body weight in grams of protein so right now you should aim for 121-162 grams of protein for optimal benefits (spread throughout the day, ideally from multiple souces). Eating (approximately) the right amount of calories and protein will be enough to keep you on the right track, most other things (timing, macros) are just preferences.
One last note. It’s important to keep your expectations in check. Losing between 0.5-1% of your total body weight each week is a good steady pace, but fluctuations will inevitably happen. Muscle growth can make this seem even slower, but don’t expect muscle growth to be the singular cause of weight gain because muscle growth is a very slow process. You might notice a difference in your physique after a month (if you take good progress photos), but don’t be discouraged if it’s hard to see. After two or three months progress should be notable. Just be consistent and do what you should and you’ll surpass your goals. Good luck!