Only last night I managed Petra in my second city on Immortal. This was playing as the Americans, so no special bonuses, and it was a late-but-not-disgustingly-late Petra - somewhere around turn 80 IIRC. I didn't just get Writing before going to Currency, I also got Mining (chopping forest, plus there was some salt around) and Calendar (giving me the happiness to grow New York as well as Washington). It should be noted, however, that I had an absolutely magnificent start - no less than five wheat within my capital's radius, two of them Flood-Plain wheat. That allowed me to get a second city out reasonably quickly and to send a couple of workers over. Also - I don't know how much of an impact this has, but it was a team game (I was trying out that West Side Story re-enactment thing). I'd imagine that might cut down on the tendency of any particular AI to hog all the wonders -or, if they have a lot of desert, to beeline Currency - when they have far less control over the tech path.