The questions you raise are some of the fundamental trade-offs between performance and flexibility of tiled services.
The short answer is: No, you can't reproject it 'on-the-fly' either at the server or client.
In my opinion, your best choice is to adopt the web-mercator alternate sphere projection. The next-best solution is to recreate the cache in the unprojected geographic coordinate system of your preference. (Notice I didn't say 'projection.')
Let me unpack my answer a bit: First you explain that you are new to ArcGIS, but I am going to assume you are NOT new to GIS. I added your two example services to ArcGIS for Desktop so I could reveal the differences between the two WKIDs of interest. WKID 102100 is a Mercator 'projection' defined simply/efficiently on top of the WGS coordinate spheroid (see screenshot 1.) The WKID 4326 is NOT a projection, it is the spherical (geographic) coordinate system (see screenshot 2.)
This difference is why I encourage you to adopt the web-mercator 'projection' -- managing geographic data has complexities and managing a tiled image service adds even more complexity once you attempt to build tiles above/below 70degrees latitude. Recall that these tiles are supposed to be rectangular, but the lines of longitude converge at the poles, so a spherical coordinate system like WKID 4326 doesn't break up into rectanglular tiles nicely. In contrast, the web-mercator projected data has already been 'flattened' to a rectangular grid. Obviously, this grid is well-suited for cache tiling.
This link explains why the WKID in screenshot 1 reads 3857 instead of 102100.
Because of how the web-mercator projection is defined, the tile images from the two services overlay each other in central latitudes...but the differences get large when we move away from the equator. If you were able to re-project the mercator tiles onto the geographic basis, annotation and linear features appear fuzzy and squashed top-to-bottom as in the screenshot below. <-- Remember that Desktop ArcGIS can do this re-projection on-the-fly, just not web.
Hopefully, all of this discussion has swayed you toward adopting the web-mercator projection as the tiling scheme for your cache. There are lots of support materials for creating your cache if you choose that alternate solution.
Good luck either way.