If you maintain a separate data structure along side your heap, this would likely solve your problem. This is the approach that the LinkedHashMap uses (a linked list along side the HashMap) to allow for an LRU cache and well known ordering of the entries in the LinkedHashMap (insertion order) (grepcode LinkedHashMap.Entry).
This data structure would look like a Deque or something similar and is ordered by insertion order. No other ordering is imposed on this structure.
The biggest problem with doing this though, is that the two structures (the heap and the deque) are not synchronized, one would have to do book keeping to remove from the deque when something is removed from the heap.
One approach to this would be to use a weak reference (Java Reference, C# WeakRefrence class). When you walk the deque you would poll the Reference for
get() to see if its actually there, and if so return that, otherwise discard that element in the deque and keep walking the list until you find a Reference that has an object attached to it.
The gotcha here is that if you are pointing to the object the heap is pointing to, it is possible that some other part of the code has taken a strong hold on the object and you'll think that is still in the Heap.
To avoid this, the deque should instead point to the heap element rather than the object the heap element is pointing to, and be very clean with your removal of the element from the heap when it is disposed (and not letting it leak outside of the heap - except to the deque (which should probably be inside the heap)). I will admit to not knowing how long the Reference will still point to something and what conditions are necessary to deterministically clear it.
This then would allow the garbage collector to do the work for you of book keeping. The trade off is instead of each time the insert or removal is being done form the heap and book keeping being done then, the book keeping is done when the deque is polled or peeked. Which way the trade off goes is something to consider based on the insertion, removal, and polling the application does of the heap.
A thought of sticking yet another data structure inside the heap may allow for issues of deterministic references. If you have a HashMap in the heap that holds all the objects too (though note that its not actually holding copies of them juts its own strong references to the objects). When something is added or removed from the heap, it is also added or removed from the HashMap. Thus, the deque, instead of holding weak references to the object holds a strong reference. When the deque is polled, it checks the HashMap to see if the object is still in the heap.
Either way, what this ultimately provides is a deque such that the first element returned from the deque is the oldest in the heap, and the last element returned from the deque is the newest object in the heap.