I took a look at Griffiths Valuation, which is a survey of Head of Households taken between 1848 and 1864. You can also search it here: https://www.failteromhat.com/griffiths.php and here: http://www.askaboutireland.ie/griffith-valuation/index.xml. Here is a sample of likely connections for, first is the name, the townland, parish and county (Mayo). Ballina was the large city nearest to these places, so often people would say they were from Ballina, but were from a small rural vilage. Note that Kilmoremoy is the Parish that Ballina is in. b
Fleming Thomas Seeaghandoo Kilfian Mayo
Fleming Richard Seeaghandoo Kilfian Mayo
Fleming Richard Cloontakillew Kilfian Mayo
Fleming Michael George's Island Killala Mayo
Fleming Michael Islands Killala Mayo
Fleming Michael Arran Street Kilmoremoy Mayo
Fleming Michael Ross (Gardiner) Killala Mayo
Fleming Edward Cloonshinnagh Ballysakeery Mayo
Fleming John Rathoma Ballysakeery Mayo
Birth records around 1855 are a bit sparse. There are some for Kilfian Parish and Kilmore Parish before, and after. Killala and Ballyskeery have records after. There's a good website that covers that part of Mayo here: http://goldenlangan.com/map.html - there are quite a number of headstones for Flemings listed there.
I will look to see if I can find any other possible close matches, but at least this may be a start for you to narrow your research.