Separate the "back-end" engine (which keeps track of board state, receives move orders from front-ends, generates random numbers to resolve battles, sends updates to front-ends, deals with saving and restoring specific games, ...) from "front-end" ones, which basically supply user interfaces for all of this.
PyGame is one suitable technology for a client-side front-end, but you could implement multiple front-ends (maybe a PyGame one, a browser-based one, a text-based one for debugging, etc, etc). The back-end of course could care less about PyGame or other UI technologies. Python is fine for most front-ends (except ones that need to be in Javascript, Actionscript, etc, if you write front-ends for browsers, Flash, etc;-) and definitely fine for thre back-end.
Run back-end and front-ends as separate processes and communicate as simply as you possibly can -- for a turn-based game (as I believe this one is), XML-RPC or some even simpler variant (JSON payloads going back and forth over HTTP POST and replies to them, say) would seem best.
I'd start with the back-end (probably using JSON for payloads, as I mentioned), as a dirt-simple WSGI server (maybe with a touch of werkzeug or the like to help out with mdidleware), and a simple-as-dirt debugging command-line client. At each step I would then be enriching either the server side (back-end) or the client side (front-end) carefully avoiding doing too-big OR any simultaneous "steps". I wouldn't use "heavy" technologies nor any big frameworks doing magical things behind my back (no ORMs, Django, SOAP, ...).
Make sure you use a good source code repository (say hg, or maybe svn if you know you'll be doing it all alone, or bazaar or git if you already know them).