PHP4 did had a set of built in XML parsing functions. You start by creating instantiating a parser, then feeding it some data to be parsed, then running another function to extract the parsed data as something such as an array structure.
You will need to do a bit of porting to make this work as it is more complicated than the replacements introduced in PHP5, but it is workable.
That being said, your world would be a happier place and your customer would have a better product if you convince them to move to a host with PHP5. They are currently paying you to make something that will make their lives more difficult down the road, their product harder to maintain and thus more expensive, and exposing themselves to other unnecessary risks.