Bonjour,

Personnellement, je pencherais pour « partir de rien ».

Est-ce que cela signifie que les deux tournures sont possibles ?

Non. « Ne partir » signifie qu’on ne part pas. Or, on part, mais de rien.

Naya a raison : l’expression consacrée est partir de rien. Elle est partie de rien et est arrivée tout en haut. 

Dict. de l’Ac. fr., s.v. Partir :

« Expr. Partir de rien, commencer dans la vie sans ressources ni soutiens. Dans la locution prépositive À partir de. Une fortune édifiée à partir de rien. En usant de, en se servant de. Un mot formé à partir de deux racines grecques. »

Partir de rien : rien est ici dans sa valeur de substantif signifiant « peu de chose », « bagatelle ».
Il n’exprime pas une négation comme dans je ne veux rien.
Il est très proche du sens de rem, (latin : accusatif du substantif res ) « chose ».

Voir le IV du TLF :
IV. − Emploi substantif
1. Chose sans importance, bagatelle. Souvent aussi ce n’est qu’un rien, quelques deniers à peine (Faral,).
N’est-ce rien que ce rien qui nous délivre de tout? (Claudel).