Not really a beginner, but a re-starter

If any of you say my intro, you'll understand this post a lot better.

I am trying to restore myself to a healthier version of myself, and although I know I'll never be 17 again I'd like to try to regain my health and wellbeing by starting down the vegan path again and eventually taking up my sport of choice: Martial Arts.

I am also a fan of yoga, as it is kind of attached to martial arts. I'm also interested in trying new sports, and although I'm not really into bodybuilding, I would like to regain some of my old strength training and perhaps get even stronger than I used to be.

So I'm trying to create a fitness and nutrition plan for myself without resorting to those fad diets or weightloss routines where you have to shell out your hard-earned green.

What are some things that have worked for any of you in achieving the goals you've set for yourself? How would you recommend I get back in teh swing of things, gradually, all at once or somewhere in between?