If the projection isn't spherical Mercator, or if there is a different tile naming system, then you can't make the same assumptions about tile names.
In general, you'd have to do a normal projection operation to find the coordinates in the projected space that correspond to the longitude/latitude of interest, then apply the rules that apply to a particular tile naming system.
The first part can be done fairly easily with a tool like proj.4.
The second part probably can't be solved in a general way. There may not even be tiles that correspond to any given longitude / latitude pair, depending on how tiles are named (e.g. for a projection based on a UTM zone, you probably don't have tiles for most of the world, because that projection is only valid for that UTM zone).