Change background map for contextily

First make sure that your GeoDataframe is in Web Mercator projection (epsg=3857). Once your Geodataframe is correctly georeferenced, you can achieve this by Geopandas reprojection:

df = df.to_crs(epsg=3857)

Once you have this done, you easily choose any of the supported map styles. A full list can be found in contextily.sources module, at the time of writing:

### Tile provider sources ###

ST_TONER = 'http://tile.stamen.com/toner/tileZ/tileX/tileY.png'
ST_TONER_HYBRID = 'http://tile.stamen.com/toner-hybrid/tileZ/tileX/tileY.png'
ST_TONER_LABELS = 'http://tile.stamen.com/toner-labels/tileZ/tileX/tileY.png'
ST_TONER_LINES = 'http://tile.stamen.com/toner-lines/tileZ/tileX/tileY.png'
ST_TONER_BACKGROUND = 'http://tile.stamen.com/toner-background/tileZ/tileX/tileY.png'
ST_TONER_LITE = 'http://tile.stamen.com/toner-lite/tileZ/tileX/tileY.png'

ST_TERRAIN = 'http://tile.stamen.com/terrain/tileZ/tileX/tileY.png'
ST_TERRAIN_LABELS = 'http://tile.stamen.com/terrain-labels/tileZ/tileX/tileY.png'
ST_TERRAIN_LINES = 'http://tile.stamen.com/terrain-lines/tileZ/tileX/tileY.png'
ST_TERRAIN_BACKGROUND = 'http://tile.stamen.com/terrain-background/tileZ/tileX/tileY.png'

ST_WATERCOLOR = 'http://tile.stamen.com/watercolor/tileZ/tileX/tileY.png'

# OpenStreetMap as an alternative
OSM_A = 'http://a.tile.openstreetmap.org/tileZ/tileX/tileY.png'
OSM_B = 'http://b.tile.openstreetmap.org/tileZ/tileX/tileY.png'
OSM_C = 'http://c.tile.openstreetmap.org/tileZ/tileX/tileY.png'

Keep in mind that you should not be adding actual x,y,z tile numbers in your tile URL (like you did in your "EDIT" example). ctx will take care of all this.

You can find a working copy-pastable example and further info at GeoPandas docs.

import contextily as ctx

# Dataframe you want to plot
gdf = GeoDataFrame(df, crs= {"init": "epsg:4326"}) # Create a georeferenced dataframe  
gdf = gdf.to_crs(epsg=3857) # reproject it in Web mercator
ax = gdf.plot()

# choose any of the supported maps from ctx.sources
ctx.add_basemap(ax, url=ctx.sources.ST_TERRAIN)
ax.set_axis_off()
plt.show()

Contextily's default crs is epsg:3857. However, your data-frame is in different CRS. Use the following,refer the manual here:

ctx.add_basemap(ax, crs='epsg:4326', source=ctx.providers.Stamen.TonerLite)

Please, refer to this link for using different sources such as Stamen.Toner, Stamen.Terrain etc. (Stamen.Terrain is used as default).

Also, you can cast your data frame to EPSG:3857 by using df.to_crs(). In this case, you should skip crs argument inside ctx.add_basemap() function.