I would use gdal_translate http://www.gdal.org/gdal_translate.html with Virtual raster (.VRT) output http://www.gdal.org/gdal_vrttut.html as an interim format.
gdal_translate -of VRT -projwin ulx uly lrx lry input.png output.vrt
Place the upper left and lower right coordinates of the bounding box as -projwin values. Notice the order which is different from BBOX which is lower left, upper right.
Now you can use the output.vrt file as input for gdal2tiles. Advantage in using VRT instead of GeoTIFF or any other image format as an interim format is that VRT is just a short XML file and no image data are copied.
You approach by attaching georeferencing into .VRT file with -a_ullr and converting VRT into tiles is right. With a little bit different command the result looks good. Actually the commands can be as simple as these:
gdal_translate -of VRT -a_srs EPSG:4326 -a_ullr 112 24 115 21 img.png output.vrt
The directory "output" contains Leaflet, OpenLayers, and Googlemaps maps. The leaflet.html one looks like this:
You may not really want to create zoom levels -z 0-4 because level zero covers the whole world and the footprint of your image is rather small. Automatically created map contains zoom levels 6-10 which suit with the size of your image better. That option -p raster does not create Leaflet and Googlemaps page may be a bug in gdal2tiles.py.