There's none in Harlem. Closest you'll come is holes-in-the-wall and kiosks that cell DJ mix CDs and oversized white t-shirts. There's a number of decent thrift stores but that's about it. Not worth the trip if all he's interested in is record shopping, but Harlem's a great place for other things.
Dunno shit about the Bronx except for the downtown courtroom district, Orchard Beach, and a couple of friends' places, but I doubt there's any record stores there. It doesn't make financial sense to open a shop up there, or in Harlem for that matter.