Can a future UK government decide to rejoin the EU without a referendum or do they have to hold one?
The UK does not have a documentary constitution. This means that there is no single piece of paper that I can refer to which sets out the details of when referendums are necessary.
Instead the UK constitution is based on statute, tradition and convention. In the case of referendums, there are two traditions, which are somewhat at odds. First there is the long tradition of "Parliamentary Sovereignty". This is the principle that Parliament can pass any act. By this principle, all that is needed to rejoin (from the UK side) is a simple act of Parliament. Secondly there is a more recent tradition (only about 50 years old) that legislation that significantly affects the constitutional state of the UK should be put out to referendum. By this principle, the UK should hold a referendum if the government wanted to rejoin the EU.
In practice, the second tradition would most likely hold. In the event of the Lib Dems or the Greens winning a majority in 2024 (stranger things have happened...), they would have done so on the basis of a manifesto promising a referendum, not on a manifesto promising immediate application for re-entry.
A future government does not have to hold a referendum, but it would so anyway.
At the risk of stating the obvious, I imagine any PM who won a general election based on a campaign pledge to rejoin would have a sufficient mandate to do so from the voters. Remember that the Brexit referendum wasn't binding to start with, though it would have been politically risky to ignore it.
When the UK joined the EC in 1973 there was no referendum. The government of Edward Heath (Conservative) signed the treaty, Parliament passed the European Communities Act 1972 (which gave EC law supremacy over UK law) and that was that.
There was a referendum in 1975 but that was after the event and called by the next government under Harold Wilson (Labour). The Labour government called a referendum partly (or mainly) because it was split on the question of EC membership. Ministers were given freedom to campaign for either side and holding a referendum was a way of taking the sting out of the issue within the Labour Party. It was never suggested that there was any constitutional requirement to hold a referendum.
That said, I think political legitimacy is more than merely following the minimum constitutional requirements and I think the public would expect a referendum if EU membership were to be considered in future and a government which took the UK into the EU without a referendum would probably pay dearly in the next general election (just as the party which advocated a second referendum because they didn't like the result of the 2016 referendum paid dearly in the 2019 general election). But there is no constitutional requirement to hold a referendum before joining or leaving the EU.