Basic fitness you can of course achieve through cardio, running and cycling from what you will say will be best for you. The couch potato to 5km program works excellently for this. You start off walking, walking briskly, jogigng and so on and build it up. Ultimately you are doing 2 speed and 1 distance day a week (ie. Running 1 mile at your best pace and the other day covering a mile and a half or two miles at a slower pace) and this way you can build up to whatever distance you want.
Strength wise, bodyweight exercises like Pressups, Chinups, Situps, Leg Raises, Calf Raises and so on can develope a good physique. The thug workout also is an excellent way to get a reasonable build:
Once you get past all the bronx attitude it proves what you can achieve. Certainly I've been trying it and it does give benefit.
Do a modified version of the Army PT Test, which is good for preparing for the PT Test, I've never scored below 290 (17 to 21 y/o age group) using this method. Basically, train the test muscles.
MWF - three sets of 35 reps of pushups (feet elevated, normal, on knees) and three sets of abs with 35 reps of crunches (feet elevated, normal) and sit ups.
TuThSat - run 3 miles. Or run 2 miles doing telephone poles (run as hard as you can between two or three sets of poles, then jog to catch your breath and then sprint again).
It's very basic and an easy way to develop some fitness before moving up to some of the harder workouts listed in previous posts. I really like the variety of workouts posted here!