If you are on VFR Flight Following you usually don’t need to ask permission to change altitudes. The exception would be if you are given an altitude to fly from ATC. For example, last week I was flying west from Corona and approaching Burbank’s airspace. While climbing through 4,000' I was given an altitude restriction of “At or below 5,000'”. ATC had me fly over Burbank’s Class C altitude (4,800') but wanted to keep me below the departing traffic. I could see a big jet pass me and once it did I was told to “resume own navigation”. On my initial call I had indicated that I was going to fly home at 6,500' so I climbed to that altitude. I could fly at any appropriate altitude, e.g. 4,500', 6,500', 8,500' etc. but given how busy the airspace is and the expectation of ATC that I would remain at 6,500' I would not change altitude unless I first arranged to do so with ATC.
On the flight into Corona, at around 15 miles from the airport, I was given instructions to fly at or below 3,000'—presumably to avoid traffic departing Ontario. There was no need to inform ATC that I was leaving 3,000' when I had the airport in sight and began my descent.
On the other hand, once I got past Ventura, the traffic volume was much lower so I wouldn’t necessarily talk to ATC if I wanted to climb to go over a mountain or avoid a cloud.
As a general rule, when you begin your descent to land ATC can figure it out. In many cases the beginning of the descent corresponds with picking up the ATIS. Since ATC likes to know that you have the ATIS I will usually combine the descent and ATIS call in one transmission.
In your specific example, since you will be flying at the wrong altitude for 30 minutes, you should either climb or descend—unless your current altitude was assigned by ATC.
FYI, in SoCal when ATC says “At or below 5,000'” they really mean “at exactly 5,000'”.