Audio file: a way to get position in miliseconds for any given byte position?

I'm streaming audio from a server to browser, Android and iOS clients. Now what I'm doing is sending the file's range in bytes requested by the client through the header Range.

My application requires synchronization so I must know the chunk's timestamp related to the file's beginning.

I did my tests with mp3 files and the conclusion from it and my web reading is that is impossible to determine the timestamp without downloading the previous data.

I'm asking based on the question MP3: a way to get position in miliseconds for any given byte position? that had a similar problem but tried to find the solution for mp3 files only and opted for a method that don't get a good precision.

Possible Solution

1. Look for other audio formats that have timestamp information in its headers/frames thought the whole file. I started to look AAC files that have something about being self-synchronized, but it may has nothing to do about determining timestamp;

2. Use file formats that doesn't have the mp3's limitations to determine timestamp given bytes position. Seems unlike due the limitation be related to compressing audio, if I use something near the raw would be much better download the whole compressed one.

3. Decode and reencode the audio files in a custom structure that has timestamp information. It's probably a creation of a new audio format, what is not my intention, there must be something similar out there.

4. Forgetting about getting the file in any position because doesn't worth the server overhead of converting every audio file to a new format. I doubt that the server's sacrifice of reencoding audio will be greater than the bandwith required to download since the beginning.

I'm glad to hear about any suggestion, discussions about the solutions, new solutions or ways to be more clear about what I want. Thank you in advance.