I would attack it in two ways:
- Keep the amount of food the same, but increase your protein intake.
- Start doing full body exercises to increase your muscle mass.
Keeping the food about the same ensures your body isn't going to substantially increase mass. Increasing the amount of protein you eat provides more raw material for your body to increase the muscle mass. However, to take advantage of the increased protein you have to do some exercise.
Full body strength work, even using nothing but body weight exercises will take advantage of the protein. Since you are demanding more strength from your body, it will build muscle to meet those demands. Since you are maintaining the same amount of food (calories), your body has to balance things out which will get rid of the excess fat.
Over time, if you really start to enjoy the strength work, you may look at increasing your body mass slowly. 56 kg (123 lb) is rather light for a man. To do that, you work on eating a little more while increasing the intensity of your exercise.
Body weight exercises
This isn't a full exercise plan, but it should be well rounded enough for you to get what you want:
Do this routine 3x a week, and do something cardiovascular for 20 minutes a day. That can be running on a treadmill, riding a bike, swimming, running outside, playing basketball, doing some form of aerobics. The choice really is yours, and having a variety of activities will help you from getting bored with one of them.
About the pullups: you might not be able to do them right away. If you can, great. However, if you can't do a pull up, start with the inverted rows until you can do 3 sets of 15 reps (3x15). From there, you should be able to follow Scooby's advice on building up your first sets of pull ups and chin ups. If you don't have a bar you can hang from, you can at least do inverted rows using a table--just make sure it can support your weight.
The idea behind the full body work to get rid of belly fat is the fact you have to get rid of overall fat. The best way to do that is to increase your muscle mass. At only 56 kg, your belly fat shouldn't be too bad so a recomposition like this should be very possible. Strength training has also been shown to improve mental health, so that should help with programming.